Merge Sort (병합 정렬)

 

참고자료: 유투버 동빈나 님의 실전 알고리즘 강좌  
               Geeks for geeks - Merge Sort

정렬방법에는 시간복잡도  $O(N^2)$ 을 갖는 Selection Sort (선택 정렬), bubble sort(버블정렬), insertion sort(삽입정렬)등이 있다. 이 방법들은 프로그래밍이 직관적이고 쉽지만 데이터의 개수의 제곱으로 계산량이 증가하기 때문에 많은 데이터를 처리해야 하는 작업에는 적합하지 않다. 이를 극복하기 지난 글에서는 위해 시간복잡도 $O(N*logN)$을 갖는 Quick Sort (퀵 정렬)에 대해서 알아보았다.

이번에는 Quick Sort와 같이 시간 복잡도 $O(N*logN)$을 갖는 분할 정복식 알고리즘(DAC)인 Merge Sort (병합 정렬)에 대해 알아보도록 하겠다. 

퀵정렬은 이미 정렬되어 있는 수의 배열을 정렬할 경우 (분할이 편향되게 되므로) 시간복잡도가 $O(N^2)$이 되는데 벙합정렬은 정확히 반절씩 나누어 정렬하기 때문에 어떠한 경우에도 시간복잡도 $O(N*logN)$을 보장한다는 장점이 있다. 병합정렬은 다음의 생각에서 출발한다.

일단 반으로 나누고 나중에 합쳐서 정렬하기

The algorithm divides the array into two halves, recursively sorts them,
and finally merges the two sorted halves.

배열을 크기가 1인 배열 상태로 나누고 이를 2개씩 합치면서 2개 배열 -> 4개 배열 -> 8개배열 ... 의 순서로 정렬을 한다. 아래의 예시로 알고리즘을 한번 이해해 보자. 

7 6 5 8 3 5 1 9          <<1개의 배열이 8개
6 7 / 5 8 / 3 5 / 1 9    <<2개의 배열이 4개
5 6 7 8 / 1 3 5 9        <<4개의 배열이 2개
1 3 5 5 6 7 8 9          <<8개의 배열이 1개

알고리즘의 pseudo code는 다음과 같다.

MergeSort(arr[], start, end)
if end > start
    1. array의 중간지점을 찾는다.
    	middle = start+(end-start)/2
    2. start부터 middle까지 (first half) mergeSort한다.
    	Call mergeSort(arr, start, middle)
    3. middle부터 end까지 (second half) mergeSort한다.
    	Call mergeSort(arr, middle+1, end)
    4. 2와 3으로 부터 정렬된 각각의 결과를 병합(Merge)한다.
    	Call merge(arr, start, middle, end)

Wikipedia에서 제공해주는 아래그림을 보면, array는 그 사이즈가 1이될때까지 recursively하게 절반으로 나누어 지고 사이즈가 1이 되고나면 정렬을 하면서 합친다. 초록색으로 표시된 step진행되는 순서를 잘 보면 이해가 쉽다.

이제 이를 c++로 구현해보자 위의 pseudo code에 따르면 결과를 병합해주는 merge함수와, 왼쪽 절반과 오른쪽 절반 각각을 정렬하는 mergeSort함수가 필요하다.

/******************************************************************************
1. 가운데 값을 찾아서 반으로 나누고
2. 합쳐서
3. 정렬하기
*******************************************************************************/
#include <iostream>
#include <vector>
using namespace std;
vector<int> sorted;

//conquer
void merge(vector<int> *data, int start, int mid, int end){
    int i = start;
    int j = mid+1;
    int k = start;

    while(i<=mid && j <= end){
        if( data->at(i) < data->at(j)){
            sorted.at(k) = data->at(i);
            i++;
        }
        else{
            sorted.at(k) = data->at(j);
            j++;
        }
        k++;
    }
    if(i > mid){
        for(int t=j; t<=end; t++){
            sorted.at(k) = data->at(t);
            k++;
        }
    }
    else{
        for(int t=i; t<=mid; t++){
            sorted.at(k) = data->at(t);
            k++;
        }
    }
    
    for(int l=start; l<=end; l++){
        data->at(l) = sorted.at(l);
    }
}

//divide
void mergeSort(vector<int> *data, int start, int end){
    //recursive loop exit condition
    // if(start >= end) return; <<이렇게 해도 됨.
    if(end>start){
        int middle = start+(end-start)/2;
        //start 부터 middle까지 mergeSort
        mergeSort(data, start, middle);
        //middle 부터 end까지 mergeSort
        mergeSort(data, middle+1, end);
        //정렬된 각각의 결과를 병합한다.
        merge(data, start, middle, end);
    }
}

int main(){
    
    int input, size = 5;
    vector<int> inputs(size);
    sorted.resize(size);
    for(int i=0; i<size; i++){
        cin >> input;
        inputs.at(i) = input;
    }
    
    mergeSort(&inputs, 0, size-1);
    
    for(int i=0; i<size; i++){
        cout << inputs.at(i) <<" ";
    }
    
    return 0;
}