병합 정렬(Merge Sort)

병합 정렬이란?

정렬하고자 하는 배열을 계속 반으로 쪼개어 잘게 나누어진 배열끼리 정렬 후 다시 합쳐서 정렬하며 완성해 나가는 과정이다.

Divide And Conquer

1단계 :: 분할(Divide) 해결이 용이한 단계까지 문제를 분할해 나간다.

2단계 :: 정복(Conquer) 해결이 용이한 수준까지 분할된 문제를 해결한다.

3단계 :: 결합(Combine) 분할해서 해결한 결과를 결합하여 마무리 한다.

MergeSort(ar, mid);

MergeSort(ar + mid, len - mid); 이 코드가 병합 정렬을 시도하기 위해 반으로 계속 나누는 과정을 이행해준다.

(왜냐면 앞의 int mid = len / 2;가 있기 때문이다.)

시간 복잡도는 T(n) = 2T(n/2) + n, T(n) = Θ(n log n) 즉, O(nlogn)이다.

#include <iostream>
 
int MergeSort(int *ar, int len)
{
    if (len < 2) return 0;
 
    int mid = len / 2;
    MergeSort(ar, mid);
    MergeSort(ar + mid, len - mid);
 
    int *buf = new int[len];
 
    int i = 0;
    int j = mid;
    int k = 0;
 
    while (i < mid && j < len)
        buf[k++] = (ar[i] < ar[j]) ? ar[i++] : ar[j++];
 
    while (i < mid)
        buf[k++] = ar[i++];
 
    while (j < len)
        buf[k++] = ar[j++];
 
    for (i = 0; i < len; i++)
        ar[i] = buf[i];
 
    delete[] buf;
}
 
 
int main(void)
{
    int arr[4] = { 3,4,2,1 };
    int i;
    int len = sizeof(arr) / sizeof(int);
 
    MergeSort(arr, len);
 
    for (i = 0; i < 4; i++)
        printf("%d ", arr[i]);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>