2-2)[C] 병합 정렬(Merge Sort)

1) 병합 정렬이란?

정렬하고 싶은 수열을 두 개의 수열로 분할해 간다. 더 이상 분할되지 않는 상태(즉, 각 그룹이 한 개의 숫자가 된 경우) 그룹들을 병합해 나간다. 병합할 때에는 정렬이 끝난 두 개의 수열을 병합해서 정렬이 끝난 하나의 수열로 만들고, 이것을 전체가 하나의 그룹이 될 때까지 반복한다.

 

2) 병합 정렬의 시간복잡도

병합 정렬에서 숫자를 분할해 갈 때는 계산 시간이 걸리지 않는다. 사실상 처음부터 분할된 상태라고 생각해도 무방하다. 

두 개의 정렬이 끝난 수열을 병합하는 부분은, 선두의 수를 비교해서 작은 쪽을 위로 올리는 것을 반복하는 것이 전부이므로 두 수열의 길이에 따라 달라진다. 따라서 하나의 층에서 병합 계산 시간은 그 층에 있는 숫자의 수가 된다.

어떤 층을 봐도 숫자는 n개 이므로 각 층의 계산 시간은 O(n)이 된다. 즉, 전체 계산 시간은 O(n log n)이다. 

 

3) 병합 정렬 구현

#include <stdio.h>

int num = 8;
int sorted[8]; // 정렬된 배열은 반드시 전역으로.

void merge(int a[], int m, int mid, int n) { // m:시작점, mid:중간점, n:끝점
	int i = m;
	int j = mid + 1;
	int k = m;
	// 작은 순서대로 배열에 삽입
	while (i <= mid && j <= n) {
		if (a[i] <= a[j]) {
			sorted[k] = a[i];
			i++;
		}
		else {
			sorted[k] = a[j];
			j++;
		}
		k++;
	}
	// 남은 데이터 삽입
	if (i > mid) {
		for (int p = j; p <= n; p++) {
			sorted[k] = a[p];
			k++;
		}
	}
	else {
		for (int p = i; p <= mid; p++) {
			sorted[k] = a[p];
			k++;
		}
	}
	// 정렬된 배열을 삽입
	for (int p = m; p <= n; p++) {
		a[p] = sorted[p];
	}
}
void mergeSort(int a[], int m, int n) { // 배열 나누는 과정
	// 크기가 1보다 큰 경우
	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 arr[8] = { 8, 2, 6, 5, 1, 4, 2, 7 };
	mergeSort(arr, 0, num - 1);
	for (int i = 0; i < num; i++) {
		printf("%d ", arr[i]);
	}
	return 0;
}

결과화면

1 2 3 4 5 6 7 8