Merge Sort (병합/합병정렬)

| Merge Sort

병합 정렬 혹은 합병 정렬이라고도 하는 Merge Sort는 시간 복잡도가 O(nlogn)인 비교 기반의 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 같은 값일 때 그 순서가 유지되는 안정 정렬에 속한다. 분할 정복 알고리즘의 일종이며, 존 폰 노이만이 1945년에 개발하였다. 

 

Merge Sort의 가장 큰 특징은, 임시로 정렬된 부분을 저장할 별도의 공간 n이 필요하다는 점과, 안정 정렬이라는 점이다. 이는 특정 문제를 해결할 때 아주 중요한 포인트가 될 것이다. 

---

| 병합 정렬의 구현

병합 정렬은 대부분 Recursive하게 구현하는 것이 이해하기도 쉽고 간단하다.

Recursive Style 1 

const int LM = 100005;
int arr[LM], tmp[LM];
void mergeSort(int start, int end) {
	// 1. base condition
	if(start >= end) return;

	// 2. devide & conquer
	int mid = (start+end) / 2;
	mergeSort(start, mid);
	mergeSort(mid+1, end);

	// 3. merge
	int i = start, j = mid + 1, k = s;
	while (i <= mid && j <= end) {
		if(arr[i] < arr[j]) {
			tmp[k++] = arr[i];
		} else {
			tmp[k++] = arr[j];
		}
	}

	while(i <= mid) tmp[k++] = arr[i++];
	while(j <= end) tmp[k++] = arr[j++];

	// 4. copy
	for(i = s, i <= e; ++i) arr[i] = tmp[i];
}

Recursive Style 2 

void merge(vector<int> &v, int start, int mid, int end) {
	vector<int> tmp(end - start + 1);

	int i = start, j = mid, k = 0;
	while(i <= mid && j <= end) {
		if(v[i] < v[j]) {
			tmp[k++] = v[i++];
		} else {
			tmp[k++] = v[j++];
		}
	}

	while(i <= mid) tmp[k++] = v[i++];
	while(j <= end) tmp[k++] = v[j++];
	
	for(i = start; i <= end; i++) 
		v[i] = tmp[i - start];
}

void mergeSort(vector<int> &v, int start, int end) {
	if(start >= end) return;

	int mid = (start + end) / 2;
	mergeSort(v, start, mid);
	mergeSort(v, mid+1, end);
	merge(v, start, mid, end);
}

두 구현방식의 차이점은 크게 없으니, 마음에 드는 방법을 사용하면 될 것 같다.