병합정렬(Merge Sort)

병합 정렬(merge sort)은 분할 정복 알고리즘을 이용해 정렬하는 알고리즘이다.

분할 정복 알고리즘(Divide And Conquer)이란?

그대로 해결할 수 없는 문제를 작은 문제로 분할하여 해결하는 방법이나 알고리즘이다.

분할 정복 알고리즘은 보통 재귀 함수를 통해 자연스럽게 구현된다.

분할 정복 알고리즘은 분할, 정렬, 결합의 3단계로 나타내지는데

병합 정렬에 3단계가 적용되는 모습은 다음과 같다.

1. 정렬하기 좋은 상태로 분할을 진행

2. 정렬하기 좋은 상태에서 정렬을 하고

3. 정렬이 완료된 조각들을 결합하여 정렬을 끝낸다.

이런 절차로 병합정렬이 이루어지는 것이다.

실제로 전체적인 과정에 대한 그림을 보이자면

다음과 같이 가장 배열의 가장 작은 단위까지 쪼개졌다가 정렬을 해가면서 올라가는 

모습을 볼 수 있다.

코드로는 다음과 같이 구현된다.

#include <stdio.h>
#include <stdlib.h>

void MergeTwoArea(int first, int mid, int last, int arr[]) {
	int * tmp;
	tmp = (int*)malloc(sizeof(int)*(last + 1));
	//정렬된 것을 임시로 저장해놓을 배열 동적할당
	int i, j, k; // i는 앞부분의 index j는 뒷부분의 index
	int start = first; int end = last; //시작과 끝 index 저장
	for (i = first, j = mid + 1; ;) { //병합할 두 영역의 데이터를 비교하여 임시배열에 저장
		if (arr[i] < arr[j]) tmp[start++] = arr[i++]; 
		else tmp[start++] = arr[j++];

		if (i == mid + 1 || j == last + 1) break;
		//두 영역중에 한 부분이 모두 임시영역에 들어갔다면 break
	}

	if (i > mid) //뒷 부분이 tmp로 모두 이동하지 않았다면 순서대로 넣어준다.
		for (k = j; k <= last; k++) tmp[start++] = arr[k];
	else //앞부분이 tmp로 이동하지 않았다면 앞부분을 순서대로 tmp에 넣어준다.
		for (k = i; k <= mid; k++) tmp[start++] = arr[k];

	for (i = first; i <= last; i++) arr[i] = tmp[i]; 
	//임시배열에서 원래의 arr배열로 옮겨서 다시 저장한다.
}
void MergeSort(int first,int last, int arr[])
{
	int mid;
	if (first < last) {
		mid = (first + last) / 2;
		MergeSort(first, mid, arr);
		MergeSort(mid + 1, last, arr);
		//분할과정

		MergeTwoArea(first, mid, last, arr);
		//정렬 및 결합과정
	}
}
int main()
{
	int arr[] = { 20, 13, 92, 57, 21, 3, 68, 45, 1 };
	int last = (sizeof(arr) / sizeof(int)) - 1; //마지막 배열의 index
	MergeSort(0, last, arr);

	for (int i = 0; i <= last; i++)
		printf("%d ", arr[i]);
}

특징

합병 정렬의 가장 큰 장점은 배열이 처음에 어떻게 정렬되어있던간에 늘 같은 시간복잡도를 

유지한다.

(이는 경우에 따라 시간복잡도가 달라질 수 있는 quick sort 와는 상반된다.)

하지만 정렬을 위해 별도의 공간을 유지해야한다는 점은 단점으로 작용한다.

시간복잡도는 nlg(n) 으로 정렬 알고리즘중에 가장 빠른 시간복잡도를 가진다.

(lg(n)은 밑이 2인 로그함수를 의미한다.)