Merge Sort - 합병 정렬과 코드

병합정렬이라고도 하고 합병정렬이라고도 한다.

합병정렬은 퀵소트와 비슷하면서도 2배의 메모리 공간을 차지한다.

하지만 최선/평균/최악의 경우 시간복잡도가 모두 O(NlogN)으로 같다.

 

합병정렬은 

1. 영역 나누기

2. 각 영역을 Merge Sort

3. 두개의 영역을 Merge

하는 순으로 진행된다. 

 

간단한 예를 그림과 함께 보면 다음과 같다.

배열을 쪼갤 수 있을 때까지 쪼갠후 합친다.

합칠 때는 값을 비교하면서 순서를 맞춰 합친다. 

 

의사코드를 작성해보면 다음과 같다.

MergeSort(start, end, arr[], tmp[]){
    if(start >= end) return;
    
    //분리
    mid = (start + end)/2;
    
    //합병정렬
    MergeSort(start, mid, arr);
    MergeSort(mid+1, end, arr);
    
    //합치기
    while(idx1 <= mid && idx2 <=end){
    	if(arr[idx1]<arr[idx2]){
        	tmp[idxtmp ++] = arr[idx1 ++ ];
        }else{
        	tmp[idxtmp ++] = arr[idx2 ++ ];
        }
    }
    while(idx1 <= mid) tmp[idxtmp++] = arr[idx1++];
    while(idx2 <= end) tmp[idxtmp++] = arr[idx2++];
    
    //합친결과 저장
    for(i = start; i <= end; i++){
    	arr[i] = tmp[i];
    }
}

 

이를 C언어로 작성해보면 다음과 같다.

#include <stdio.h>
#include <string.h>

//오름차순 정렬
void merge_sort(int start, int end, int arr[], int tmp[]){
    if(start >= end) return;
    int mid = (start+end)/2;

    merge_sort(start, mid, arr, tmp);
    merge_sort(mid+1, end, arr, tmp);

    int idx1 = start, idx2=mid+1, idxtmp = start;
    while(idx1 <= mid && idx2 <= end){
        if(arr[idx1] < arr[idx2]){
            tmp[idxtmp++] = arr[idx1++];
        }else{
            tmp[idxtmp++] = arr[idx2++];
        }
    }
    while(idx1<=mid){
        tmp[idxtmp++] = arr[idx1++];
    }
    while(idx2<=end){
        tmp[idxtmp++] = arr[idx2++];
    }

    int i;
    for(i=start; i<=end; i++){
        arr[i] = tmp[i];
    }
}

int main(void)
{
    int i;
    const int N = 5;
    int arr[N], tmp[N];
    for(i = 0; i < N; ++i){
        scanf("%d", arr + i);
    }
    merge_sort(0, N-1, arr, tmp);

    for(i = 0; i < N; ++i){
        printf("%d ", arr[i]);
    }
}