병합 정렬 (Merge Sort)

(출처: Introduction to Algorithms)

 

병합 정렬(Merge Sort, 머지 소트)에 대해 알아봅시다. 병합 정렬은 분할정복 기법을 이용한 정렬 방법입니다.

• 분할: 정렬할 n개 원소의 배열을 n/2개씩 부분수열 두 개로 분할
• 정복: 병합 정렬을 이용해 두 부분 배열을 재귀적으로 정렬
• 결합: 정렬된 두 개의 부분 배열을 병합해 정렬된 배열 하나로 만듦

 

Fig 1. 정렬된 두 부분 수열을 병합하는 예시

병합 정렬 알고리즘의 핵심은 결합 단계에서 정렬된 두 부분 수열을 병합하는 것입니다.

병합할 원소의 개수를 n개라고 하면 병합 작업에는 O(n) 시간이 걸립니다. 두 부분 수열에서 한개씩 비교해서 더 작은걸 빼면 되니 많아야 n번 비교를 하게 됩니다.

Fig 1.은 부분 수열 병합 과정을 보여줍니다. 절반만큼 나눠서 각각 배열을 만들어서 옮겨두고, 이때 배열 맨 끝에 한 칸씩 추가해 INF(\(\infty\))값을 넣습니다. 이 값을 이용해 알고리즘을 단순화할 수 있습니다.

 

Fig 2. A[p, q], A[q+1, r]을 병합하는 프로시저

A[p, q]와 A[q+1, r]이 정렬되어 있다고 가정하고 이를 병합해 원래 부분 배열 A[p, r]을 대체하는 Merge 프로시저입니다.

 

Fig 3. A[p, r]을 정렬하는 프로시저

부분 배열 A[p, r]을 정렬하는 Merge sort 프로시저입니다. 재귀적으로 왼쪽, 오른쪽 부분 배열을 정렬한 후 Merge 프로시저를 호출해 정렬된 부분 배열 두개를 합칩니다.

 

 

const int INF = INT_MAX;

void merge(vector<int>& v, int left, int mid, int right) {
	int left_sz = mid - left + 1;
	int right_sz = right - mid;

	vector<int> L(left_sz + 1), R(right_sz + 1);
	for (int i = 0; i < left_sz; ++i)
		L[i] = v[left + i];
	for (int j = 0; j < right_sz; ++j)
		R[j] = v[mid + j + 1];

	L[left_sz] = INF;
	R[right_sz] = INF;

	int i = 0, j = 0;
	for (int k = left; k <= right; ++k) {
		if (L[i] <= R[j]) {
			v[k] = L[i];
			++i;
		}
		else {
			v[k] = R[j];
			++j;
		}
	}
}

void merge_sort(vector<int>& v, int left, int right) {
	if (left < right) {
		int mid = (left + right) / 2;
		merge_sort(v, left, mid);
		merge_sort(v, mid+1, right);
		merge(v, left, mid, right);	// 정렬된 두 부분 수열을 병합
	}
}

C++로 위 수도코드를 구현했습니다.

책에서 배열 인덱스는 1부터 시작하는 점을 유의해주세요.