#3 병합 정렬(Merge Sort)

一心一德，贯彻始终 한마음 한뜻으로, 처음부터 끝까지 꾸준하라 - 삼민주의가(三民主義歌)

 

이번에는 병합 정렬(Merge Sort)에 대해 학습한다. 폰 노이만 선생이 개발한 알고리즘으로 유명. 보통 O(nlogn) 정렬들을 학습할 때 제일 먼저 학습하게 된다. 합병 정렬하고 같은 거니까 괜히 헷갈리지 말자.

 

텍스트적으로 설명하자면... 

 

주어진 배열을 반으로 나눈 다음 각각을 재귀적으로 정렬하고, 그 후에 정렬된 두 배열을 병합하여 전체 배열을 정렬하는 방법이라고 보면 된다. 분할 정복(divide / conquer)로 구현된다. 당연히 처음 본 사람은 무슨 소린가 싶을 것이다..

 

 

일단은 분리하는 것을 divide, 합치는 것을 conquer이라고 하자. conquer 상에서는 정렬이 이루어진다. conquer을 반복한 결과 오름차순으로 정렬이 이루어진다는 것.

 

이런 궁금증이 생길 수도 있다. 요소가 2개 이상인 부분 리스트는 어떻게 Conquer이 진행되는 것일까?

 

또 하나의 리스트를 만들어 진행하게 된다. 이 sorted list를 원본 list에 복사함으로써 정렬 과정이 끝나게 되는 것.

이제 C++로 구현해보자

 

#include <iostream>
#include <vector>

using namespace std;

// 두 개의 배열을 병합하는 함수
void merge(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // 임시 배열 생성
    vector<int> L(n1), R(n2);

    // 두 개의 배열에 데이터 복사
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    // 두 개의 배열을 병합
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // 남은 요소들 복사
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// 병합 정렬 함수
void mergeSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        // 왼쪽과 오른쪽 반을 나누어 재귀적으로 정렬
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // 정렬된 두 배열을 병합
        merge(arr, left, mid, right);
    }
}

int main() {
    vector<int> arr = { 12, 11, 13, 5, 6, 7 };
    int n = arr.size();

    cout << "원래 배열: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;

    mergeSort(arr, 0, n - 1);

    cout << "정렬된 배열: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;

    return 0;
}