[정렬] 합병 정렬

작성일 | In

작동 방식

이전 글에서 설명했던 퀵 정렬과 같이 합병 정렬도 분할 정복 기법을 사용합니다.

합병정렬 과정을 크게 3가지로 쪼개면,

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

조금 더 자세히 설명하면,

  1. 리스트의 길이가 0, 또는 1 이면 이미 정렬된 것으로 본다.
  2. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
  3. 각 부분 리스트를 재귀적으로 합병정렬을 이용해 정렬한다.
  4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병(merge)한다.

작동 과정

{1, 7, 5, 3, 4, 2, 6, 8} 과 같은 리스트(배열)이 있다고 가정합시다.
먼저 리스트를 두 개로 분할합니다.
-> {1, 7, 5, 3} {4, 2, 6, 8}
아직 리스트의 크기가 1보다 크기 때문에 또 분할합니다.
-> {1, 7} {5, 3} {4, 2} {6, 8}
한번 더 분할합니다.
-> {1}, {7}, {5}, {3}, {4}, {2}, {6}, {8}

크기가 1이므로 각각의 부분 리스트를 정렬이 됐습니다.
이제 정복 차례입니다.
1, 7을 합쳐서 정렬하면 {1, 7}
5, 3을 합쳐서 정렬하면 {3, 5}
4, 2를 합쳐서 정렬하면 {2, 4}
6, 8을 합쳐서 정렬하면 {6, 8}

정복을 한번 더 하면
1, 7, 3, 5 를 정렬하면 {1, 3, 5, 7}
2, 4, 6, 8 을 정렬하면 {2, 4, 6, 8}

마지막으로 전체를 합쳐서 정렬하면 {1, 2, 3, 4, 5, 6, 7, 8} 이 나옵니다.

구현

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
#include <stdio.h>

const int n = 8;

void merge(int arr[], int p, int q, int r){ //정복
    int i = p, j = q+1, k = p;
    int tmp[n] = {0};
    while(i <= q || j <= r){
        if(i > q) tmp[k++] = arr[j++];
        else if(j > r) tmp[k++] = arr[i++];
        else if(arr[i] <= arr[j]) tmp[k++] = arr[i++];
        else tmp[k++] = arr[j++];
    }
    for(int i=p; i<=r; i++) arr[i] = tmp[i];
}

void mergeSort(int arr[], int p, int r){ //분할
    if(p<r){
        int q = (p+r)/2;
        mergeSort(arr, p, q);
        mergeSort(arr, q+1, r);
        merge(arr, p, q, r);
    }
}

int main(){
    int arr[n] = {1, 3, 5, 7, 2, 4, 6, 8};
    mergeSort(arr, 0, n-1);
    for(int i=0; i<n; i++) printf("%d ", arr[i]);
}

시간 복잡도 분석

합병 정렬의 시간 복잡도를 분석해봅시다.
먼저, merge함수는 재귀 호출 트리의 각 단계에서 시간 복잡도의 합은 Θ(n)이라는 것은 자명합니다.
합병 정렬은 매번 2로 나누기 때문에 재귀 호출 트리의 깊이는 Θ(log2)입니다.
그러므로 Θ(n) * Θ(log2) ∈ Θ(n log n)입니다.