병합 정렬(Merge Sort)이란?

Merge Sort(병합 정렬)

병합 정렬은 분할정복(Divide and Conquer)의 대표적인 예이다. n개의 데이터를 가진 배열을 오름차순으로 정렬하기 위해 병합정렬을 사용한다면 아래와 같은 3단계의 과정을 거치게 된다. 

 

1. Divide(분할) : n개의 원소를 갖는 배열을 n/2 개의 원소를 갖는 작은배열 2개로 나눈다.
2. Conquer(정복) : 각각의 작은 배열들을 정렬한다. 
3. Combine(병합) : 정렬된 작은 배열들을 병합한다. 

 

예를 들어 다음과 같은 과정을 거치게 된다. 

 

 

병합정렬의 특징

• 병합정렬은 분할한 작은 배열을 위한 저장공간이 따로 필요하다. n개의 원소를 n/2 개씩 나누므로 병합정렬의 공간복잡도는 O(n)이다. 따라서 not-in place 정렬이다.
• 시간 복잡도는 O(nlogn)이다.
• 삽입 정렬은 중복된 키 값의 순서가 정렬 후에도 유지되므로 stable 정렬이다.

소스코드

void merge(int arr[], int left, int mid, int right) {
    int i, j, k, l;
    i = left;
    j = mid + 1;
    k = left;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j])
            sorted[k++] = arr[i++];
        else
            sorted[k++] = arr[j++];
    }

    if (i > mid) {
        for (l = j; l <= right; l++) 
            sorted[k++] = arr[l];
        
    }
    else {
        for (l = i; l <= mid; l++)
            sorted[k++] = arr[l];
    }

    for (l = left; l <= right; l++) {
        arr[l] = sorted[l];
    }
}

void merge_sort(int arr[], int left, int right) {
    int mid;
    if (left < right) {
        mid = (left + right) / 2;
        merge_sort(arr, left, mid);
        merge_sort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}