Merge Sort [병합정렬]

병합정렬은 분할정복을 이용한 sort algorithm입니다.

먼저 배열을 1개 단위로 쪼갠 뒤, 다시 합치며 정렬하는 방법입니다.

코드는 다음과 같습니다.

void merge(int S[], int U[], int low, int mid, int high){
    int i=low, j=mid+1, k=low;
    while(i<=mid && j<=high){
        if(S[i]<S[j]) U[k] = S[i++];
        else U[k] = S[j++];
        k++;
    }
    if(i>mid){
        while(j<=high) U[k++] = S[j++];
    }
    else{
        while(i<=mid) U[k++] = S[i++];
    }
    while(low<=high){S[low]=U[low]; low++;}
}

void mergeSort(int S[], int U[], int low, int high){
    if(low<high){
        int mid = (low+high)/2;
        mergeSort(S,U,low,mid);
        mergeSort(S,U,mid+1,high);
        merge(S,U,low,mid,high);
    }
}

merge 함수는 분리되었던 두 부분을 합치는 것입니다. (정복)

merge

위 코드에서 두 부분은 S 배열에서 low:mid, mid+1:high로 나뉩니다.

두 부분은 합쳐지면서 정렬되는데, 각 부분 앞에서부터 비교해가며 작은 것을 앞에서부터 U 배열에 채워 넣습니다.

전부 채워 넣은 후, S 배열에 U 배열을 복제합니다. (low:high 만)

 

mergeSort 함수는 mid를 기준으로 low:mid, mid+1:high를 재귀호출한 후 나누어진 부분을 합치기 위해 merge함수를 호출합니다.

merge sort 그림

위 그림과 같이 파티션이 전부 나누어지면, 그때부터 병합되기 시작합니다. 코드를 따라가며 직접 그려보시면 이해가 쉽게 되실 것이라 생각합니다.

 

다음은 worst time complexity(최악의 경우 시간 복잡도)입니다.

따라서 merge sort의 worst time complexity는 𝜃(nlg(n))입니다.