Algorithm] 합병 정렬(Merge Sort)

Algorithm] 합병 정렬(Merge Sort)

합병 정렬은 대표적인 분할정복 방법(Divide and Conquer)을 사용한다.

더 이상 부분 문제로 만들 수 없는 수준까지 분할한 뒤,

이를 다시 취합하는 과정에서(정복) 정렬이 이루어지는 정렬 알고리즘이다.

일단 백문이불여일견이니 이것이 작동하는 과정을 그림으로 한 번 살펴보자.

파란색은 정렬이 완료되지 않은 부분문제, 즉 분할 대상이고

주황색은 정렬이 완료된 부분문제로 정복 및 정복 대상이다.

과정을 보면 알 수 있듯, 다시 한 번 말하지만 합병 정렬은 정복 과정에서 정렬이 이루어진다.

의사 코드를 한 번 살펴보자.

MergeSort(arr,start,end)

입력 : arr[start] ~ arr[end]

출력 : 정렬된 arr[start] ~ arr[end]

if(start<end) {

mid=(start+end)/2 // 분할을 위한 변수

MergeSort(arr,start,mid) // 분할

MergeSort(arr,mid+1,end) // 분할

Merge(arr,start,mid,end) // 합병(정복)

}

의사 코드 자체는 별 것이 없어보인다.

분할 정복에 대해서 이해만 완벽하다면 MergeSort 함수 구현 보다는

Merge(합병) 함수를 구현이 더 어렵게 느껴질 수가 있다.

#include <iostream>
using namespace std;
 
void PrintList(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }
    cout << "\n";
}
 
void Merge(int arr[], int start, int mid, int end)
{
    // start index : start
    int i, j, k;
    int n1 = mid - start + 1;
    int n2 = end - mid;
    int* arr1;
    int* arr2;
 
    // Temp array
    arr1 = new int[n1];
    arr2 = new int[n2];
    for (i = 0; i < n1; i++)
    {
        arr1[i] = arr[start + i];
    }
    for (i = 0; i < n2; i++)
    {
        arr2[i] = arr[mid + 1 + i];
    }
 
    // compare array
    i = 0, j = 0, k = start;
    while (i < n1 && j < n2)
    {
        if (arr1[i] < arr2[j])
        {
            arr[k] = arr1[i];
            i++;
        }
        else
        {
            arr[k] = arr2[j];
            j++;
        }
        k++;
    }
 
    // clear array
    while (i < n1)
    {
        arr[k] = arr1[i];
        i++, k++;
    }
    while (j < n2)
    {
        arr[k] = arr2[j];
        j++, k++;
    }
 
    delete arr1;
    delete arr2;
}
 
void MergeSort(int arr[], int start, int end)
{
    int mid;
    if (start < end)
    {
        // Divide
        mid = (start + end) / 2;
        MergeSort(arr, start, mid);
        MergeSort(arr, mid + 1, end);
        // Conquer
        Merge(arr, start, mid, end);
    }
}
 
int main(void)
{
    int n;
    int* arr;
 
    cin >> n;
    arr = new int[n];
 
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
 
    MergeSort(arr, 0, n - 1);
 
    PrintList(arr, n);
    
    delete arr;
    return 0;
}

합병정렬에 대해서 알아두어야 할 부분이 하나 더 남았다.

정렬의 성능에 관한 부분인데,

합병 정렬은 분할 정복 방식으로 어떠한 경우에도 동일하게 작동하기 때문에

최악과 최적의 경우에 차이를 보이지 않고 시간 복잡도는 O(nlogn)으로 동일하다.

합병정렬이 가지고 있는 특이한 점이 하나 있다.

바로 공간 복잡도에 대한 부분이다.

흔히 알고리즘을 판단할 때, 속도(시간)의 문제만 다루다 보니,

공간 복잡도에 대해서는 전혀 고려하지 않는 책들도 많은 편인데

합병 정렬은 퀵정렬, 버블정렬 등과는 다르게 공간 복잡도에 대한 개념을 다룰 필요가 있다.

분할 후 합병 과정에서 임시로 결과를 저장할 공간이 필요하며,

공간 복잡도 O(n)으로 O(1)인 다른 정렬들과는 다른 양상을 보인다.

합병정렬은 외부 정렬에서 기본이 되는 알고리즘이다.

뿐만 아니라, 연결 리스트에서는 퀵이나 힙에 비해서 효율적으로 운용이 가능하며,

멀티 코어 CPU, GPU 등에서 정렬 알고리즘을 병렬화하는 과정에서 이를 사용하니,

사용 용처에 대해서도 알아두자.