[알고리즘/C] 합병 정렬(merge sort)

합병 정렬이란?

합병 정렬(merge sort)은 하나의 배열을 두 개의 균등한 크기로 분할하고 각 분할된 배열을 정렬한 다음, 두 개의 정렬된 부분 배열을 합하여 전체가 정렬된 배열을 얻고자 하는 것이다.

 

※ 합병 정렬은 분할정복기법(divide and conquer)에 바탕을 두고있다. 분할 정복 기법은 문제를 작은 2개의 문제로 분리하여 그 문제를 각각 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.

 

합병 정렬에서의 분할 정복 기법은,

1. 분할(divide) : 중간 크기를 구하여 이를 기준으로 2개의 부분 배열로 분할한다.
2. 정복(conquer) : 각각의 부분 배열을 정렬한다.
3. 병합(combine) : 정렬된 부분 배열들을 하나의 배열로 통합한다.

 

합병 정렬은 순환 알고리즘을 적용할 수 있는데, mergeSort라는 분할된 배열을 정렬하는 함수와 merge라는 정렬된 배열을 합하여 정렬된 하나의 배열을 만드는 함수로 이루어진다.

 

 

 

void merge(int list[], int low, int middle, int high) {
	int i = low;
	int j = middle + 1;
	int t = 0;

	int temp_list[MAX_SIZE]; //정렬된 배열을 만들기 위한 별도의 임시 배열 생성

	while (i <= middle && j <= high) { //두 배열에 모두 요소가 남아있을 경우
		if (list[i] <= list[j])
			temp_list[t++] = list[i++];
		else
			temp_list[t++] = list[j++];
	}

	while (i <= middle) { //왼쪽이 남았을때
		temp_list[t++] = list[i++];
	}

	while (j <= high) { //오른쪽이 남았을때
		temp_list[t++] = list[j++];
	}

	t = 0;
	for (int k = low; k <= high; k++) {
		list[k] = temp_list[t++]; //원래의 리스트에 복사
	}

}

void merge_sort(int list[], int p, int r) {
	int q;
	if (p < r) {
		q = (p + r) / 2; //분할
		merge_sort(list, p, q);  //정렬
		merge_sort(list, q + 1, r);
		merge(list, p, q, r); //병합
	}
}

 

시간복잡도

• 배열의 크기가 2^3=8일경우, 배열을 분할하면서 횟수가 늘어날수록 부분 배열의 크기가 2^3->2^2->2^1->2^0순으로 줄어든다. 즉, 분할 횟수가 k라고 하면 $$k={log}_{2}n$$이다.
• 부분 배열로 나누어지는 단계에서는 비교나 이동 연산이 수행되지 않지만, merge 함수에서 비교나 이동 연산이 수행된다. 
• 비교 횟수: 크기가 1인 부분 배열 2개를 합병하는 데는 최대 2개의 비교 연산이 필요하고, 부분 배열의 쌍이 4개이므로 2*4 = 8번의 비교 연산이 필요하다. 크기가 2인 부분 배열 2개를 합칠 때 최대 4번의 비교 연산이 필요하고 부분 배열의 쌍이 2쌍이 있으므로 4*2 = 8번의 비교 연산이 필요하다. 즉, 하나의 합병단게에서는 n번의 비교 연산이 있으므로 총 비교 횟수는 $$n{log}_{2}n$$ 이다.
• 이동 횟수: 임시 배열에 복사 후 다시 가져오므로 총 요소의 갯수가 n인 경우 레코드의 이동이 2n번 일어난다. 따라서 총 이동 횟수는 $$2n{log}_{2}n$$이다.
• 즉, 시간 복잡도는 최악 평균 최선의 경우 상관없이 $$O(n{log}_{2}n)$$이다.
• 합병 정렬은 이와같이 데이터의 분포에 영향을 덜 받는다는 장점이 있지만, 임시 배열을 하나 더 만들기 때문에 공간 복잡도는 좋지않다. 또한 레코드의 크기가 큰 경우에는 이동 횟수가 많아 많은 시간이 든다.