[알고리즘] 자바에서의 병합 정렬

병합 정렬(Merge Sort)

- 재귀 용법을 활용한 정렬 알고리즘

 

1. 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.

2. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.

3. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

 

* 분할 정복 알고리즘의 대표적인 예시 중 하나이다.

* 병합 정렬은 하나의 함수를 가지고 재귀 호출을 했던 지금까지 와는 달리 함수 2개를 가지고 재귀 호출을 하는 알고리즘이다.

    - 하나는 리스트를 절반으로 자르는 함수

    - 또 하나는 정렬된 리스트를 정렬해서 병합해주는 함수

 

자바 코드로 직접 살펴보자.

일단 전체 코드는 이렇게 된다.

- MergeSort.java

import java.util.ArrayList;
import java.util.List;

public class MergeSort {
	public static void main(String[] args) {
		List<Integer> list = new ArrayList<Integer>();
		list.add(3);
		list.add(6);
		list.add(17);
		list.add(1);
		list.add(9);
		list.add(5);
		list.add(4);
		
		System.out.println(splitAndmerge(list).toString());
	}

	private static List<Integer> splitAndmerge(List<Integer> list) {
		if(list.size() <= 1)
			return list;
		
		int half = list.size() / 2;
		List<Integer> leftList = splitAndmerge(list.subList(0, half));
		List<Integer> rightList = splitAndmerge(list.subList(half, list.size()));
		
		return listMerge(leftList, rightList);
	}

	private static List<Integer> listMerge(List<Integer> leftList, List<Integer> rightList) {
		List<Integer> mergeList = new ArrayList<Integer>();
		
		int leftIndex = 0; int rightIndex = 0;
		while(leftList.size() > leftIndex && rightList.size() > rightIndex) {
			
			int leftElement = leftList.get(leftIndex);
			int rightElement = rightList.get(rightIndex);
			
			if(leftElement > rightElement) {
				mergeList.add(rightElement);
				rightIndex++;
			}
			else {
				mergeList.add(leftElement);
				leftIndex++;
			}
		}
		
		while(leftList.size() > leftIndex) {
			mergeList.add(leftList.get(leftIndex));
			leftIndex++;
		}
		
		while(rightList.size() > rightIndex) {
			mergeList.add(rightList.get(rightIndex));
			rightIndex++;
		}
		return mergeList;
	}
}

 

이제 여기서 리스트를 잘라주는 메소드를 살펴보자.

private static List<Integer> splitAndmerge(List<Integer> list) {
	if(list.size() <= 1)
		return list;
		
	int half = list.size() / 2;
	List<Integer> leftList = splitAndmerge(list.subList(0, half));
	List<Integer> rightList = splitAndmerge(list.subList(half, list.size()));
		
	return listMerge(leftList, rightList);
}

- 리스트의 길이가 1 이하이면 해당 리스트를 리턴해준다.

- 그렇지 않으면 리스트의 크기를 반으로 나눈 값을 구한 후 subList() 메소드를 이용해 해당 크기를 기준으로 왼쪽, 오른쪽으로 자른 부분 리스트를 splitAndmerge() 메소드의 재귀 호출 파라미터로 적재한다.

- leftList, rightList 결과를 받고 나면 두 부분 리스트를 listMerge() 메소드에서 병합시킨다.

 

* 재귀 과정 설명

1. 일단 처음엔 리스트의 길이가 반드시 1 보다 클 때를 가정해야 한다. 그렇다면 첫 호출 때 해당 리스트의 길이를 2로 나눈 값을 구해서 왼쪽, 오른쪽 부분 리스트를 만들게 될 것이다.

2. 해당 부분 리스트들을 파라미터로 하여 splitAndmerge() 메소드를 재귀 호출한다, 이때 리스트들의 길이가 1 이하가 되기 전까지 계속 splitAndmerge() 메소드가 재귀 호출 되면서 점점 리스트들이 쪼개진다.

3. 계속 리스트들이 절반으로 쪼개지다가 길이가 1 이하가 되는 시점이 오면 해당 리스트를 직접 반환 하는것을 시작으로 지금 까지 재귀 용법으로 호출되던 메소드들이, 프로그램 진행 프로세스 스택의 가장 위에서 부터 차례대로 값을 반환받기 시작한다. 

4. 길이가 1 이하가 되어 리스트를 직접 반환 받은 이후엔, 반환받은 리스트가 각각 leftList, rightList 에 적재되면서 listMerge() 메소드를 실행하여 반환값을 받는것으로 자신보다 상위의 재귀 호출 메소드에 값을 전달해주는 것이다.

5. 물론 그 상위의 재귀 메소드는 listMerge() 메소드 반환값을 다시 leftList, rightList 에 적재한 후, 또 다시 listMerge() 메소드 결과값을 자신의 상위 호출 메소드로 돌려주는 방식으로 진행된다.

6. 이와 같은 과정을 반복하다가 스택의 가장 끝에 있는 재귀 메소드까지 listMerge() 메소드를 수행하면 해당 결과값은 최초에 splitAndmerge() 메소드를 호출한 곳으로 반환되면서 최종적으로 병합 정렬을 이용하여 정렬된 리스트를 얻게 되는 것이다.

 

다음은 두 개의 부분 리스트를 받아서 정렬한 후 병합해주는 메소드이다.

private static List<Integer> listMerge(List<Integer> leftList, List<Integer> rightList) {
	List<Integer> mergeList = new ArrayList<Integer>();
		
	int leftIndex = 0; int rightIndex = 0;
	while(leftList.size() > leftIndex && rightList.size() > rightIndex) {
			
		int leftElement = leftList.get(leftIndex);
		int rightElement = rightList.get(rightIndex);
			
		if(leftElement > rightElement) {
			mergeList.add(rightElement);
			rightIndex++;
		}
		else {
			mergeList.add(leftElement);
			leftIndex++;
		}
	}
		
	while(leftList.size() > leftIndex) {
		mergeList.add(leftList.get(leftIndex));
		leftIndex++;
	}
		
	while(rightList.size() > rightIndex) {
		mergeList.add(rightList.get(rightIndex));
		rightIndex++;
	}
	return mergeList;
}

- 입력 받은 두 부분리스트 첫번째 인덱스부터 비교를 시작하여 더 큰 값을 병합을 위한 리스트에 추가해주는 방식으로 정렬을 수행한다.

- 그러다가 한 쪽 부분 리스트가 다 병합 리스트에 들어가서 다른 한 쪽이 남았다면, 남아있는 다른 한쪽은 추가적으로 더 비교과정을 거치지 않고 남아있는 데이터들을 모두 병합 리스트에 추가해준다.

- 그렇게 해서 완성된 병합 리스트를 반환한다.

 

 

알고리즘 분석

- 각 단계는 항상 O(n), 그리고 단계는 항상 log2n 개 만큼 만들어 지므로 O(log n)

- 최종적으로 모든 단계를 총합한 시간 복잡도는 O(n) * O(log n) = O(nlog n) 이다.