병합 정렬

개요

병합 정렬_{Merge Sort}은 존 폰 노이만이 제안한 정렬 알고리즘으로, 하나의 리스트를 두 개의 균등한 크기의 리스트로 분할하고, 그 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻는 방법이다.

동작

병합 정렬은 분할 정복_{Divide and Conquer} 기법에 바탕을 둔 방법으로, 다음의 단계들로 이루어진다.

1. 분할_Divide: 리스트를 같은 크기의 2개의 부분 배열로 분할한다.
   • 리스트의 길이가 0이나 1이면 이미 정렬된 것으로 본다.
2. 정복Conquer: 부분 리스트를 정렬한다.
3. 결합Combine: 정렬된 부분 배열들을 하나의 배열에 통합한다.

시간 복잡도

최악, 평균, 최선의 시간 복잡도가 모두 동일하다.

• 최선의 경우: $O(n\log n)$
• 최악의 경우: $O(n\log n)$
• 평균적인 경우: $O(n\log n)$

분석

비교 연산

• 순환 호출의 깊이 (병합 단계의 수)
  • 데이터의 개수 $n$이 2의 거듭제곱($2^k$)이라고 가정하면, 매 분할 단계에서 절반으로 나누어지므로 $2^k\to 2^{k-1}\to \cdots \to 2^0$이 되어 순환 호출의 깊이는 $k$가 된다.
  • 여기서 $n=2^k$이므로, $k={\log }_{2}n$이다.
• 각 병합 단계에서의 비교 연산
  • 하나의 병합 단계에서는 최대 $n$번의 비교 연산이 필요하다.
• 따라서 총 비교 연산은 최대 $n{\log }_{2}n$번 필요하다.

이동 연산

• 각 병합 단계에서 임시 배열에 복사했다가 다시 가져와야 하므로 전체 데이터의 개수를 $n$이라 했을 때, 하나의 병합 단계에 $2n$개의 이동 연산이 필요하다
• 전체 병합 단계의 수는 앞에서 다뤘듯 ${\log }_{2}n$이므로, 총 $2{\log }_{2}n$개의 이동 연산이 필요하다.
• 따라서 이동 연산 또한 $O(n\log n)$의 복잡도를 가진다.

특징

• 안정성을 만족한다.
• 비제자리 정렬이다.
  • 단, 구현에 따라서 제자리 정렬이 될 수 있다.
• 장점
  • 데이터의 분포가 어떻든 간에, 정렬에 걸리는 시간은 동일하다.
• 단점
  • 임시 배열이 필요하다. ($O(n)$의 공간 복잡도)
  • 데이터의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래한다.

구현

리스트를 실제로 2개의 리스트로 분할하는 것이 아니라, 인덱스를 기준으로 리스트를 나눈 것처럼 간주해 병합 정렬을 수행한다는 점에 유념하면 이하 코드의 이해에 도움이 될 것이다.

public static class MergeSort {
	public static void sort(int[] array, int left, int right) {
		if (left < right) {
			int mid = (left + right) / 2;
			sort(array, left, mid);
			sort(array, mid + 1, right);
			merge(array, left, mid, right);
		}
	}
	private static void merge(int[] array, int left, int mid, int right) {
		int[] tempArray = new int[array.length];
 
		int i = left; // 정렬된 왼쪽 리스트에 대한 인덱스
		int j = mid + 1; // 정렬된 오른쪽 리스트에 대한 인덱스
		int k = left; // 정렬될 리스트에 대한 인덱스
 
		// 분할 정렬된 두 리스트의 병합
		while (i <= mid && j <= right) {
			if (array[i] <= array[j]) // 오름차순 정렬
				tempArray[k++] = array[i++];
			else
				tempArray[k++] = array[j++];
		}
 
		int l;
		// 남아 있는 데이터 복사
		if (i > mid) {
			for (l = j; l <= right; l++)
				tempArray[k++] = array[l];
		} else {
			for (l = i; l <= mid; l++)
				tempArray[k++] = array[l];
		}
 
		// 병합된 임시 리스트를 원래 리스트에 복사
		for (l = left; l <= right; l++)
			array[l] = tempArray[l];
	}
}

참고문헌

• 천인국, 공용해, 하상호, 『C언어로 쉽게 풀어쓴 자료구조』(개정 3판), 생능출판(2020)
• 기계인간 John Grib, 병합 정렬 (Merge Sort), 2023.04.02, https://johngrib.github.io/wiki/algorithm/merge-sort