[알고리즘] 정렬 - 1. 병합 정렬(Merge Sort)

1. 병합 정렬 ; Merge Sort

1.1 개념

분할 정복 알고리즘을 이용한 대표적인 정렬 방법 중 하나로, 여러 정렬된 집합들을 병합하여 하나의 정렬된 집합으로 만드는 정렬방법을 의미한다. 병합 정렬은 다음 세 가지의 단계를 통해 진행된다.

 

1. 분할(Divide) : 큰 집합을 부분집합으로 분할

2. 정복(Conquer) : 부분집합 내의 원소 정렬

3. 결합(Combine) : 정렬된 부분집합들을 하나의 집합으로 정렬하여 결합

 

원리만 생각하면 복잡해 보이지만, 그림과 함께 보면 쉽게 이해할 수 있다.

정렬되지 않은 집합 A는 다음과 같이 구성되어있다.

A = { 3, 8, 7, 2, 5, 1, 4, 6 }

집합 A를 오름차순으로 정렬한다고 가정을 해보자. 병합 정렬하는 과정은 아래 그림과 같다.

 

병합 정렬 과정

집합 A를 더 이상 분해되지 않는 가장 작은 크기의 부분집합으로 분할한 다음(1~4단계), 배열을 합치는(결합) 과정에서 오름차순을 유지하며 정렬한다(5~7단계). 이 때 집합 몇 개를 결합하여 하나의 집합으로 만들 것인지에 따라 n-way 병합이라고 부르는데, 위의 예시로 든 병합 방법은 두 개의 집합을 결합하여 하나의 집합으로 만들었기 때문에 2-way 병합 정렬이다.

 

1.2 구현

코드는 크게 두 함수로 나눌 수 있다. 정렬을 실행하는 merge() 함수와 분할과 정렬을 재귀적으로 호출하는 mergeSort() 함수로 나뉜다. 병합 정렬의 시간 복잡도는 항상 O(n log n)으로 최악의 경우 O(n^2)의 시간복잡도를 갖는 퀵 정렬에 비해 빠른 장점이 있지만, 추가적인 배열 공간이 필요하기 때문에 메모리 사용이 비효율적일 수 있다.

 

#1. merge(int* sorted, int* arr, int begin, int mid, int end)

void merge(int* sorted, int* arr, int begin, int mid, int end) {
    int i, j, k;
    i = begin;		// 첫 번째 부분집합의 첫 번째 원소
    j = mid + 1;	// 두 번째 부분집합의 첫 번째 원소
    k = begin;		// 병합할 집합의 첫 번째 원소

    while(i <= mid && j <= end) {
        if(arr[i] <= arr[j]) {
            sorted[k] = arr[i];
            i++;
        }
        else {
            sorted[k] = arr[j];
            j++;
        }
        k++;
    }
    if(i > mid) {
        for(int a = j; a <= end; a++, k++)
            sorted[k] = arr[a];
    }
    else {
        for(int a = i; a <= mid; a++, k++)
            sorted[k] = arr[a];
    }

    for(int a = begin; a <= end; a++)
        arr[a] = sorted[a];
}

 

#2. mergeSort(int* sorted, int* arr, int begin, int end)

void mergeSort(int* sorted, int* arr, int begin, int end) {
    int mid;
    if(begin < end) {
        mid = (begin + end) / 2;
        mergeSort(sorted, arr, begin, mid);	// 왼쪽 부분집합 분할
        mergeSort(sorted, arr, mid + 1, end);	// 오른쪽 부분집합 분할
        merge(sorted, arr, begin, mid, end);	// 부분집합 병합
    }
}