합병 정렬 (Merge sort)

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

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

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

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

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

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

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

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

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

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

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

합병 정렬 의사 코드

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

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++ 코드를 작성하면 다음과 같습니다.

#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 봄학기 알고리즘 - 부경대 권오흠 교수님