[알고리즘] 합병 정렬(Merge sort) 란 - travelbeeee

안녕하세요, 여행벌입니다.

오늘은 합병정렬(Merge sort)에 대해서 포스팅해보겠습니다.

---

합병 정렬의 원리

 합병 정렬은 존 폰 노이만이 개발한 정렬 알고리즘입니다.

 

 합병 정렬은 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법으로 분할 정복에 바탕을 두고 있습니다. 즉, 주어진 리스트를 크기가 1이 될 때까지 분할한 후 각각의 부분 리스트들을 정렬하면서 합병해나가 최종적으로 정렬된 리스트를 얻는 방법입니다.

 

 합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병하는 단계입니다. 이때, 새로운 리스트를 추가로 필요로 합니다. 합병 알고리즘은 2개의 리스트의 요소들을 처음부터 하나씩 비교하여 두 개의 리스트의 요소 중에서 더 작은 요소를 새로운 리스트로 옮깁니다. 둘 중에서 하나가 끝날 때까지 이 과정을 되풀이하고 만약 둘 중에서 하나의 리스트 순회가 먼저 끝나게 되면 나머지 리스트의 요소들을 전부 새로운 리스트로 복사해 정렬된 합병 리스트를 얻습니다.

 

 합병 정렬은 분할 → 정렬 → 합병 의 과정을 반복하며 배열을 정렬해나가는 알고리즘입니다.

---

합병 정렬 예시

[ 5 3 8 4 1 6 2 7 ] 리스트를 합병 정렬을 통해 정렬해보겠습니다.

 먼저, 주어진 리스트를 크기를 동일하게 균등 분열하는 과정을 반복해 크기가 1인 부분 배열들을 얻어냅니다.

 그 후, 이 부분 배열들을 정렬하며 합병해 최종적으로 정렬된 배열을 얻습니다.

 (2) 배열 A와 배열 B를 정렬하며 합병하면 [ 3 5 ] 로 이루어진 배열 AB를 얻을 수 있고, 같은 방법으로 배열 CD, EF, GH 를 얻을 수 있습니다.

 (3) 배열 AB와 배열 CD를 정렬하며 합병하면 [ 3 4 5 8 ] 로 이루어진 배열 ABCD를 얻을 수 있고, 같은 방법으로 배열 EFGH를 얻을 수 있습니다.

 (4) 마지막으로 배열 ABCD와 배열 EFGH를 정렬하며 합병하면 정렬된 전체 배열을 얻을 수 있습니다.

 2개의 부분 배열이 어떻게 정렬되고 합병되는지 자세히 다뤄보도록 하겠습니다.

 배열 A [ 3 4 5 8 ] 과 배열 B [ 1 2 6 7 ] 을 합병 정렬 알고리즘을 이용해 합병해보겠습니다.

 합병 정렬은 새로운 리스트가 필요하므로 새로운 리스트를 배열 C라고 하겠습니다. 배열 A와 배열 B의 요소들을 순회하며 더 작은 값인 '1' 을 배열 C에 저장합니다.

  배열 A와 배열 B의 요소들을 순회하며 더 작은 값인 '2' 를 배열 C에 저장합니다.

 배열 A와 배열 B의 요소들을 순회하며 더 작은 값인 '3' 을 배열 C에 저장합니다.

 같은 과정을 반복하면 다음과 같이 정렬된 합병 배열 C를 얻을 수 있습니다.

---

합병 정렬 코드

int sorted[MAX_SIZE]; // 새로운 배열 C

void merge(int list[], int left, int mid, int right) {
	int i, j, k, l;
	i = left; j = mid + 1; k = left;

	while (i <= mid && j <= right) {
		if (list[i] <= list[j])
			sorted[k++] = list[i++];
		else
			sorted[k++] = list[j++];
	}
	if (i > mid)
		for (l = j; l <= right; l++)
			sorted[k++] = list[l];
	else
		for (l = i; l <= mid; l++)
			sorted[k++] = list[l];
	// 새로운 배열 C를 다시 원래 배열로 옮긴다.
	for (l = left; l <= right; l++)
		list[l] = sorted[l];
	return;
}

void merge_sort(int list[], int left, int right) {
	int mid = (left + right) / 2;
	if (left < right) {
		merge_sort(list, left, mid);
		merge_sort(list, mid + 1, right);
		merge(list, left, mid, right);
	}
	return;
}

merge_sort로 배열을 계속 반으로 분할해주고 분할이 완료되면 merge 함수를 호출해 정렬과 합병을 진행합니다.

---

합병 정렬의 복잡도 분석

 합병 정렬은 퀵 정렬과 마찬가지로 레코드의 개수가 n 이라고 한다면 절반씩 나눠지며 분할하므로 log(n) 번의 분할 연산이 진행됩니다. 그 후 merge 함수에서 비교 연산과 이동 연산이 수행되는데 비교 연산은 최대 n 번 발생하고, 이동 연산은 2n번 발생하는 것을 알 수 있습니다. 즉, O( nlogn ) 시간 복잡도를 가지게 됩니다.

 

 단점으로는 임시 배열이 필요하므로 추가적인 메모리가 요구됩니다. 또,  이동 횟수가 많으므로 레코드들의 크기가 큰 경우에는 매우 큰 시간 장비를 초래하게 됩니다. 하지만 연결리스트를 활용해 구현한다면 레코드의 크기가 큰 경우도 문제가 되지 않는다. 퀵 정렬과 다르게 항상 균등하게 분할되므로 최악의 경우에 퀵 정렬보다 더 잘 작동합니다.

 

---

합병 정렬의 안정성

 합병 정렬은 같은 값이 있는 경우에도 같은 값들의 정렬 순서가 변하지 않는 안정 정렬에 해당합니다.

---

이상으로 합병 정렬 포스팅을 마치겠습니다.