합병 정렬 (Merge sort)

분할정복법과 합병 정렬 (Merge sort)

합병 정렬은 앞서 알아본 선택, 삽입, 버블 정렬과는 다르게 분할정복법이라는 개념을 사용합니다.

**분할정복법(Divide-And-Conquer)**이라는 것은 주어진 문제를 다음과 같은 3단계의 절차를 통해 해결하는 방법입니다.

  1. 분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할한다.
  2. 정복 : 각각의 작은 문제를 순환적으로 해결한다.
  3. 합병 : 작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구한다.

그럼 이를 토대로 합병 정렬의 과정을 살펴보겠습니다.

합병 정렬은 여러 개의 데이터를 한 번에 정렬하는 것이 아닌 이를 계속해서 반으로 나눈 후 다시 합병하는 과정에서 정렬이 이루어집니다.

분할을 반복하다보면 마지막은 길이가 1인 구간으로 나뉘어집니다. 더이상 분할이 불가능할때 다시 합병하면서 정렬을 하는것입니다. 그렇기 때문에 합병 정렬에서 가장 중요한 부분은 실제 정렬을 수행하는 **합병(merge)**하는 과정입니다.

그럼 합병과정에서 정렬은 어떻게 이루어질까요? 다음 그림을 통해서 실제 정렬이 이루어지는 합병 과정을 좀 더 자세히 알아보겠습니다.

먼저 위 그림은 합병이 이루어 지기 위한 이미 정렬된 2개의 블록이 존재하는 모습입니다. 현재 두개의 블록은 이미 길이가 1인 구간으로 나눠진 배열부터 시작해 각각 합병 과정을 거쳐 정렬된 상태로 만들어진 배열입니다.
이 두개의 블록을 정렬된 상태를 유지하며 합치기 위해서는 i 인덱스에 있는 값과, j 인덱스에 있는 값을 하나씩 비교한 후 추가배열에 저장하면 됩니다.

위 그림처럼 하나의 블록이 모두 합쳐 졌을 경우 나머지 블록은 순서대로 배열에 저장하면 됩니다.

모든 합병을 마친 후 이 추가배열의 값으로 기존 배열의 해당 구간에 복사하면 됩니다.

합병 정렬 의사 코드

의사 코드는 다음과 같습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
mergeSort(A[],p,r){
if(p<r) then{
q <- (p+r)/2;
mergeSort(A,p,q);
mergeSort(A,q+1,r);
merge(A, p, q, r);
}
}

merge(A[], p, q, r){
정렬되어 있는 ㅜ 배열 A[p..q]와 A[q+1...r]을 합하여
정렬된 하나의 배열 A[p...r]을 만든다.
}

합병 정렬 c++ 코드

이제 의사 코드를 바탕으로 c++ 코드를 작성하면 다음과 같습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>

#define ITEM_SIZE 10

using namespace std;

void print_arr(int a[], int size) {
for (int i = 0; i < size; i++) {
cout << a[i] << ' ';
}
cout << '\n';
}

void merge(int a[], int left, int mid, int right) {
int i, j, k;

i = left;
j = mid + 1;
k = left;

int tmp_arr[ITEM_SIZE];

// left 부터 mid 까지의 블록과 mid + 1 부터 right 까지의 블록을 서로 비교
while (i <= mid && j <= right) {
if (a[i] <= a[j]) {
tmp_arr[k] = a[i];
i++;
}
else {
tmp_arr[k] = a[j];
j++;
}
k++;
}

// left 블록의 값이 다 처리되었지만, right 블록의 index가 남아 있는 경우
// right 블록의 남은 부분을 순차적으로 tmp_arr에 복사
if (i > mid) {
for (int m = j; m <= right; m++) {
tmp_arr[k] = a[m];
k++;
}
}
// left 블록의 남은 부분을 순차적으로 tmp_arr에 복사
else {
for (int m = i; m <= mid; m++) {
tmp_arr[k] = a[m];
k++;
}
}

// 임시 배열인 tmp_arr의 값을 원본 배열에 복사한다.
for (int m = left; m <= right; m++) {
a[m] = tmp_arr[m];
}
}

void merge_sort(int a[], int left, int right) {
int mid;

if (left < right) {
// 절반으로 나누기 위해 중간 위치 찾기
mid = (left + right) / 2;

// 분할
merge_sort(a, left, mid);
merge_sort(a, mid + 1, right);

// 합병
merge(a, left, mid, right);
}
}

int main() {
int a[ITEM_SIZE] = { 15, 2, 24, 18, 7, 13, 12, 4, 21, 9 };
print_arr(a, ITEM_SIZE);
merge_sort(a, 0, ITEM_SIZE - 1);
print_arr(a, ITEM_SIZE);
return 0;
}

합병 정렬 시간 복잡도

이제 마지막으로 합병 정렬의 시간 복잡도를 알아보겠습니다. 데이터가 n개 일때 합병 정렬로 계산하는 시간을 T(n)이라고 하겠습니다.
정렬을 위해서 반으로 분할한 후 n/2개의 블럭에 재귀함수를 호출하면, 반으로 분할된 블럭 2개에 대한 정렬을 수행해야하므로 **T(n/2) + T(n/2)**의 시간이 걸립니다. 두개의 정렬된 블럭을 merge할 때 두 블럭을 한번씩 비교하므로 merge 시간은 n입니다.
따라서, merge sort의 시간 복잡도는 T(n) = T(n/2) + T(n/2) + n이 됩니다.

결국 분할을 반복하면 위와 같은 그림의 식을 도출할 수 있고, 이 식을 수학적으로 풀어보면 **O(nlogn)**이 됩니다.

합병 정렬과 퀵 정렬 비교

아직 퀵 정렬에 대해 다루지 않았지만 합병 정렬과 퀵 정렬 모두 시간 복잡도로 **O(nlogn)**을 갖습니다. 그러나 퀵 정렬과 합병 정렬에는 서로 다른 특징이 있습니다.

합병 정렬은 합병 과정에서 임시적인 저장공간으로 데이터를 담고 있는 배열과 같은 크기인 추가 배열을 사용하기 때문에 **추가적인 메모리가 필요**합니다. 그러나 퀵 정렬은 추가 메모리를 사용하지 않고 내부 교환만으로 수행되는 차이가 있습니다.

또한 합병 정렬은 어떤 상황이라도 항상 **O(nlogn)**의 시간 복잡도를 갖지만 퀵 정렬의 경우 아이러니하게도 정렬하기 위해 정렬이 되어 있는 데이터를 사용할 경우 **O(n^2)**의 시간복잡도를 갖게 됩니다. (이 경우는 다음에 퀵 정렬에 대해 포스팅하며 알아보겠습니다.) 그러나 최악의 경우가 아닐 경우 일반적으로 퀵 정렬이 합병 정렬에 비해 빠른 성능을 보입니다.

합병 정렬은 퀵 정렬보다 성능이 전반적으로 떨어지고, 데이터 크기만한 메모리가 더 필요하지만 최대의 장점은 **stable sort**라는 점입니다. 퀵 정렬의 경우 만약 배열 A[25] = 100, A[33] = 100 인 정수형 배열을 정렬한다고 할 때, 33번째에 있던 100이 25번째에 있던 100보다 앞으로 오는 경우가 생길 수 있습니다. 그에 반해서 합병 정렬은 이전의 순서를 유지하면서 정렬된 상태를 만들 수 있습니다.

출처 : 2015 봄학기 알고리즘 - 부경대 권오흠 교수님