[정렬 알고리즘] 03 합병 정렬(Merge Sort)이론 및 구현

1. 합병 정렬 개념

• 존 폰 노이만(John von Neumann)이 개발한 정렬 알고리즘
• 비교 기반 정렬이며 분할 정복을 통해 정렬을 수행함
• 일반적인 방법으로 구현할 때 안정 정렬에 속함
• 임시로 저장할 리스트나 배열이 필요로 함
• 입력 자료들을 원소가 하나가 될 때까지 분할한 후, 합치는 과정에서 비교하여 정렬 수행

* 합병 정렬은 다음과 같은 분할 정복을 통해 정렬을 수행함

① 분할 : 정렬할 $n$개 원소의 배열을 $n/2$개씩 부분 수열 두 개로 분할
② 정복 : 합병 정렬을 이용하여 두 부분 배열을 재귀적으로 정렬
③ 결합 : 정렬된 두 개의 부분 배열을 병합하여 정렬된 배열 하나로 만듦 

---

2. 합병 정렬 예제

비교 횟수 최대 $(n-1)$번 발생

---

3. 합병 정렬 특성

1) 장점

• 안정적인 정렬 알고리즘
• 자료구조를 리스트로 구성하면 링크 인덱스만 변경되므로 데이터 이동은 현저히 감소
• 데이터의 분포에 영향을 덜 받으므로 입력된 자료들에 영향을 받지 않고 정렬되는 시간 동일

2) 단점

• 병합하는 과정에서 입력 자료들의 크기($n$)만큼의 메모리가 추가적으로 필요
• 만약, 자료구조를 배열로 구성할 경우 입력 자료의 크기가 크게 되면 이동횟수가 많아 낭비

 

---

4. 합병 정렬 분석

▶ Pseudo code(의사코드)

* MERGE_SORT(A, p, r)은 subArray A[p, ..., r]의 원소들을 정렬
* p $\le$ r이면, 부분 배열이 많아야 한 개의 원소로 구성되므로 이미 정렬됨
* MERGE(A, p, q, r)은 이미 정렬된 부분 배열 A[p, ..., q], A[q+1, .., r]을 합병 -> $\theta(n)$시간 수행

 

※ 먼저 $T(n)$을 입력 크기가 $n$인 문제에 대한 수행시간으로 정함

① 분할 : 부분배열의 중간 위치 계산이므로 상수시간 -> $\theta(1)$
② 정복 : 두 부분문제 재귀적으로 해결, 각 부분 문제는 크기가 $n/2$이므로 $2T(n/2)$의 수행시간
③ 결합 : n개의 원소에 대해 비교횟수 최대 $n-1$번 발생 -> $\theta(n)$

 

합병 정렬의 수행시간 = $T(n)$ $=$ $\cases{ \Theta(1) & $\text{if } n=1$\cr 2T(n/2) + \theta(1) +\theta(n) & $\text{if n>1}$}$

 

Recurrence식이 나왔으므로 재귀 트리를 이용하여 시간 복잡도를 구함 ->(치환법을 통한 증명은 생략)

재귀 트리 확장 

모든 레벨의 비용은 $cn$이며 깊이는 $\lg n$이므로 재귀 트리의 총 비용은 $n \lg n$이다.

따라서, $2T(n/2) = O(n \lg n)$이며 결합시 발생하는 비용은 $\theta(n)$이지만 $O(n \lg n)$이 $\theta(n)$보다 크므로 제외한다.

 

$\therefore O(n \lg n)$

 

---

5. 합병 정렬 시간 복잡도

1) Worst Case

① Recursion Tree의 깊이 : $\lg n$

② 각 level의 비용 : $n$

③ 시간 복잡도 : $O(n \lg n)$

 

2) 성능 및 평가

• 항상 동일한 성능 보장
• 근처의 원소들과 비교하여 병합하므로 안정성 보장
• 따라서, 평균적으로 $O(n \lg n)$의 성능을 보임

	Best	Avg	Worst
합병 정렬	$O(n \lg n)$	$O(n \lg n)$	$O(n \lg n)$

---

6. 합병 정렬 구현(C언어)

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

void merge_sort(int[], int*, int, int);
void merge(int[], int*, int, int, int);

int main()
{
	int length;
	int arr[10] = { 10, 28, 30, 2, 15, 8, 67, 45, 3, 11 };
	int *temp;

	length = sizeof(arr) / sizeof(int);	
	temp = malloc(sizeof(int)*length);

	merge_sort(arr, temp, 0, length-1);
    	free(temp);
    
	return 0;
}

// 합병 정렬 함수
void merge_sort(int arr[], int *temp, int left, int right) {

	int mid;

	if (left < right) {	// 배열의 크기가 1일때까지.
		mid = (left + right) / 2;
		merge_sort(arr, temp, left, mid);	// 왼쪽부터 배열을 반으로 쪼개줌.
		merge_sort(arr, temp, mid + 1, right);	// 오른쪽 배열을 반으로 쪼개줌.
		merge(arr, temp, left, mid, right);	// 합병.
	}
}

// 합병 함수
void merge(int arr[], int *sorted, int left, int mid, int right) {

	int i = left, j = mid + 1, k = left, l;

	while (i <= mid && j <= right) {	// 중간을 기준으로 왼쪽과 오른쪽배열을 나눔.
		if (arr[i] <= arr[j])		// 오른쪽 배열이 클 경우 임시배열에 값을 저장 후 후위증가.
			sorted[k++] = arr[i++];
		else				// 또는 왼쪽 배열이 클 경우.
			sorted[k++] = arr[j++];
	}
	while (i <= mid) sorted[k++] = arr[i++];
	while (j <= right) sorted[k++] = arr[j++];
	for (l = left; l <= right; l++)		// arr 배열에 다시 임시배열에 저장된 값을 저장.
		arr[l] = sorted[l];
}