병합 정렬(Merge Sort)

퀵소트와 마찬가지로 분할정복 알고리즘이다.
재귀함수를 이용해 배열을 절반으로 잘라가며 분할하고 정복한다.

#include <iostream>
using namespace std;

int arr[10];

void merge(int a[], int m, int mid, int n) {
	int i = m;
	int j = mid + 1;
	int k = m;
	while(i <= mid && j <= n) {
		if(a[i] <= a[j]) {
			arr[k] = a[i];
			i++;
		} else {
			arr[k] = a[j];
			j++;
		}
		k++;
	}
	if(i > mid) {
		for(int t = j; t <= n; t++) {
			arr[k] = a[t];
			k++;
		}
	} else {
		for(int t = i; t <= mid; t++) {
			arr[k] = a[t];
			k++;
		}
	}
	for(int t = m; t <= n; t++) {
		a[t] = arr[t];
	}
}

void mergeSort(int a[], int m, int n) {
	if(m < n) {
		int mid = (m + n) / 2;
		mergeSort(a, m, mid);
		mergeSort(a, mid + 1, n);
		merge(a, m, mid, n);
	}
}

int main() {
	int array[10] = {10,5,4,6,2,3,7,9,1,8};
	mergeSort(array, 0, 9);
	for(int i = 0; i < 10; i++)
		cout << array[i] << " ";
}

위 코드에서 mergeSort()함수는 재귀함수로써 배열을 절반으로 나눠가며 merge()함수를 호출하고, merge()함수에서는 요소들을 비교하며 정렬하는 정복 과정을 수행한다.

mergeSort()는 분할, merge()는 정복의 역할을 한다.

피봇에 따라 성능이 다른 퀵소트와 다르게 무조건 절반으로 분할하기 때문에 모든 경우에서 O(NlogN)의 시간복잡도를 보장받는다.
다만 데이터를 담을 추가적인 공간이 필요하기 때문에 메모리 측면에서 비효율적이다.

algorithm	average	worst	best	space
merge	O(NlogN)	O(NlogN)	O(NlogN)	O(n)