[예제] 합병 정렬 (Merge Sort)

▶ 시간 복잡도 O(N × log2N)

▶ 참고: 합병 정렬(Merge Sort)  

합병 정렬(Merge Sort)

#include <stdio.h>

const int N = 7;
int arr[N] = {5, 9, 7, 1, 3, 8, 2}, temp[N];

void mergeSort(int start, int end) {
    // 0. base condition
    if (start >= end) return;

    // 1. divide
    int mid = (start + end) / 2;

    // 2. conquer
    mergeSort(start, mid);
    mergeSort(mid + 1, end);

    // 3. merge
    int i = start, j = mid + 1, k = start;
    while (i <= mid && j <= end) {
        if (arr[i] < arr[j])
            temp[k++] = arr[i++];
        else
            temp[k++] = arr[j++];
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= end) temp[k++] = arr[j++];

    // 4. copy
    for (i = start; i <= end; ++i) {
        arr[i] = temp[i];
    }
}

int main() {
    mergeSort(0, N - 1);
}

퀵 정렬도 마찬가지로 평균 시간복잡도 O(n log n)를 가지지만 Input Data의 상태에 따라 O(n²)이 될 수 있습니다.

특정 PS에서는 overflow가 발생할 수 있습니다.

또한 보다 구현하기도 쉽기 때문에 비교적 안정한 Merge Sort를 문제에서 활용

 

구현 시 Tip

① 분할하기 위해서 재귀적으로 divide 할 때,

    끝나는 조건은 원소가 1개만 남아 있는 경우 입니다.

    즉, start == end인 경우 원소가 1개이므로 start >= end 조건으로 처리합니다.

② 중간 지점을 mid로 잡고 (start ~ mid), (mid + 1 ~ end)까지 divide 합니다.

③ 단계에서 각 단계의 start, end까지 정렬하며 merge 합니다.

     k = start, i = start, j = mid + 1 

④ i (=start) ~ mid까지, j (=mid + 1) ~ end까지 비교하며 위치를 맞춰줍니다.