개념

분할 정복(Divide and conquer) 알고리즘의 한 종류로, 주어진 리스트를 부분 리스트로 나누고 오름차순(혹은 내림차순)으로 정렬이 될 수 있게 합쳐나가며 전체 리스트를 재귀적으로 정렬하는 알고리즘이다.

특징

최선, 최악, 평균 모든 케이스에서 O(nlogn)의 시간복잡도를 가지고 있으며, 정렬 알고리즘 중 최적의 복잡도를 가지고 있다.

추가적인 배열이 필요하기 때문에 O(n)의 공간 복잡도를 가지고 있어 메모리 사용이 중요한 분야에서는 비효울적일 수 있다.

기존의 상대적인 위치가 정렬 후에도 유지되는 안정 정렬(stable sort)이다.

구현

재귀적으로 부분 리스트들을 정렬해나가며, 합병 시 각 인덱스들을 비교하여 정렬된 리스트로 합치는 것이 중요하다.

#include<stdio.h>
#define N 8
int sortedList[N]; //합병용 임시 공간 
void merge(int list[], int left, int mid, int right)
{
	//합병할 배열의 인덱스로 사용할 변수들  
	
	int leftCounter = left, rightCounter = mid+1, sortedCounter = left, counter;
	
	//앞부분 배열과 뒷부분 배열을 비교하여 정렬된 순서로 합병 
	while(leftCounter<=mid && rightCounter<=right)//한쪽 배열이 완전히 사용될때까지 반복 
	{
		if(list[leftCounter] <= list[rightCounter])
			sortedList[sortedCounter++] = list[leftCounter++];
		else
			sortedList[sortedCounter++] = list[rightCounter++];
	}
	 
	//한쪽 배열이 완전히 사용되면 나머지 배열은 전부 정렬된 상태이므로 그대로 사용 
	if(leftCounter>mid)
	{
		for(counter=rightCounter; counter<=right; counter++)
			sortedList[sortedCounter++] = list[counter];
	}
	else
	{
		for(counter=leftCounter; counter<=mid; counter++)
			sortedList[sortedCounter++] = list[counter];
	}
	
	
	for(counter=left; counter<=right; counter++)
	{
		list[counter] = sortedList[counter];
	}
}
void mergeSort(int a[], int p, int q)
{
	int k;//배열을 나눌 중앙 값 
	if(p<q) //배열 원소 수 체크 
	{
		k = (p+q)/2;
		mergeSort(a, p, k); //배열의 앞 부분 정렬 
		mergeSort(a, k+1, q); //배열의 뒷 부분 정렬 
		merge(a, p, k, q);	//정렬된 배열 병합 
	}
 	//재귀적으로 리스트를 분할정복하여 최종 정렬함 
}
int main()
{
	int a[N] = {37, 10, 22, 30, 35, 13, 25, 24};
	mergeSort(a, 0, N-1);
	int i;
	for(i=0; i<N; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}