Merge Sort (합병 정렬)

Merge Sort는 배열의 값을 정렬하는 여러 가지 방법 중에 하나이다. Merge Sort는 정렬이 된 부분 배열들을 합쳐가면서 정렬을 수행한다. 정렬이 된 배열들을 합친다는 것이 Merge Sort의 핵심 아이디어이다. 이 아이디어를 이용하여 어떻게 전체 배열에 대해 정렬을 수행할 수 있을까? Merge Sort (합병 정렬)로 배열을 정렬하는 방법에 대해 알아보자. 참고로 이 글에서는 오름차순으로 정렬할 것이다.

Merge

정렬에 대해 생각하기 전에, 정렬이 된 두 배열을 합치는 작업에 대해 생각해보자. 함수 merge가 이 작업을 수행한다고 해보자. merge의 입력으로 들어오는 두 배열은 이미 정렬이 되어 있어야 하고 반환하는 결과물도 정렬이 되어 있어야 한다. 사실, 두 배열이 정렬이 되어있을 때 이 둘을 합쳐서 정렬이 된 배열을 만드는 것은 어렵지 않다. 그저 두 배열에서 반환될 배열에 아직 들어가지 않은 요소들 중 가장 앞의 값들만 비교해가며 넣어주면 된다.

아래 사진과 같이 정렬된 배열 A, B를 합친다고 하자.

1. 처음에는 두 배열의 가장 앞에 있는 값을 비교하여 작은 값을 먼저 반환될 배열에 넣는다. 즉, A[0]과 B[0]을 비교한다. A[0] 이 더 작기 때문에 반환될 배열의 첫 번째 요소에 A[0]을 넣어주자.
   
2. 1번 단계에서 A[0] < B[0] 이었기 때문에 반환될 배열의 첫 번째 요소에 A[0]이 들어가게 되었다. 이제 A[1] 과 B[0]을 비교하여 더 작은 값을 반환될 배열의 두 번째 값으로 정한다.
   
3. 이제 A[1]과 B[1]을 비교하여 더 작은 값을 배열에 넣어준다.
   
4. A[1]과 B[2]을 비교하여 더 작은 값을 배열에 넣어준다.
   
5. 이렇게 진행하다 보면 둘 중 하나의 배열의 값들이 모두 반환될 배열에 들어가게 되는 경우가 생긴다. 이제 두 배열의 값끼리 비교하는 것은 그만둔다. 그리고 나머지 남은 값들을 남은 자리에 모두 넣어준다.
   
6. 두 개의 정렬되어있던 배열이 합쳐졌다. 합쳐진 배열도 정렬이 되어있다.
   

각각의 배열의 앞에서부터 값을 비교해가며 알맞은 값을 차례로 집어넣음으로 두 배열을 성공적으로 합칠 수 있었다. 아제 c언어로 적어보자.

void merge(int* src1, int* src2, int n1, int n2, int* dest){
    // src1, src2 : 정렬된 배열
    // n1, n2 : src1, src2의 길이
    // dest : 결과를 받을 배열

    int p1 = 0; // src1에 접근 시 사용
    int p2 = 0; // src2에 접근 시 사용
    int p = 0;  // dest에 접근 시 사용

    // 합치기
    while(p1 < n1 && p2 < n2){
        if(src1[p1] < src2[p2]){
            dest[p++] = src1[p1++];
        }else{
            dest[p++] = src2[p2++];
        }
    }

    while(p1 < n1){
            dest[p++] = src1[p1++];
    }

    while(p2 < n2){
            dest[p++] = src2[p2++];
    }

}

Merge Sort 합병정렬

이제 merge를 할 수 있으니 이를 이용하여 Merge Sort를 해보자. merge와 재귀의 아이디어를 사용하면 쉽게 구현할 수 있다. 아래 Pseudocode를 보자.

1. 입력으로 들어온 배열의 크기가 1과 같거나 작으면 아무것도 수행하지 않고 종료한다. 크기가 1 이하인 배열은 그 자체로 이미 정렬된 배열이라고 할 수 있기 때문에 아무것도 수행하지 않아도 된다.
2. 입력으로 들어온 배열을 둘로 나눈다.
3. 둘로 나눈 배열에 대해 Merge Sort를 각각 수행한다.
4. 정렬이 완료된 두 배열을 merge로 합친다.아래 사진은 위의 과정을 시각화한 것이다.
5. Merge Sort는 내부에서 배열을 반으로 나눈다. 나누어진 배열에 대해서도 Merge Sort를 호출한다. 이렇게 계속 Merge Sort를 호출하다 보면 어느 단계에서의 Merge Sort는 크기가 1 이하인 배열을 받게 되어 어느 작업도 수행하지 않는다. 이 크기가 1인 배열은 위에서 언급하였듯 정렬이 된 배열로 볼 수 있다. 이 Merge Sort를 호출한 바로 직전단계의 Merge Sort는 merge를 통해 이 배열을 합친다. 그리고 이 합쳐진 결과물들을 자신을 호출하였던 Merge Sort가 계속 merge 해준다. 이 단계를 거치다 보면 결국 최초 호출하였던 Merge Sort에 값이 전달되고, 여기서 merge를 수행해 줌으로 전체 배열의 정렬이 수행되는 것이다.

이를 코드로 구현해보자. 아래 구현 코드에는 배열을 임시 배열에 복사하는 과정이 포함되어 있다.

void mergeSort(int* arr,const int n){
    // arr : 정렬을 수행할 배열
    // n : arr의 크기

    if(n<2) return;

    int h = n/2;

    int* temp = malloc(sizeof(int)*n);
    copy(arr,temp,n);

    mergeSort(temp,h);
    mergeSort(temp+h,n-h);

    merge(temp,temp+h,h,n-h,arr);

    free(temp);
}

이제 결과물을 확인해보자.

arr0
Before : 42
After  : 42
arr1
Before : 1 -3 4 2 -1 8 5 3
After  : -3 -1 1 2 3 4 5 8 
arr2
Before : 3 1 6 9 2 -5 3 6 1 5 -4
After  : -5 -4 1 1 2 3 3 5 6 6 9

MergeSort가 작동하고 있다.

시간복잡도

MergeSort의 시간 복잡도는 $O(nlogn)$이다. MergeSort 내에서 merge와 배열의 복사 과정은 배열의 길이와 선형 시간 관계이다. 이런 MergeSort를 내부에서 반으로 쪼개진 배열 두 개에 대해 다시 호출하게 된다. 즉, $n/2$ 길이의 배열에 대해 MergeSort가 두 번 호출되게 된다. n/4길이 배열에 대한 Merge Sort는 전체적으로 4번, $n/8$은 8번 호출될 것이다. $n/(2^x)$ 길이의 배열에 대해선 Merge Sort가 $2^x$번 호출된다. MergeSort로 들어오는 입력이 계속 쪼개지다 보면 언젠가 $n/(2^x) = 1$ 일 때가 올 것이다. 여기서 $x$는 $log(n)$이다.

$T(n)$
$= n + 2T(n/2) $
$= n + 2(n/2 + 2T(n/4))$
$= 2n + 4T(n/4)$
$= 2n + 4(n/4 + 2T(n/8))$
$= 3n + 8T(n/8)$
$= xn + 2^xT(n/2^x)$
$= nlog(n) + nT(1)$

$\therefore O(T(n)) = O(nlog(n))$

전체 코드

#include <stdio.h>
#include <stdlib.h>

void printArray(int* arr,int n){
    for(int i=0;i<n;++i){
        printf("%d ",arr[i]);
    }
    printf("\n");
}

void copy(int* src,int* dst,int n){
    for(int i=0;i<n;++i){
        dst[i]=src[i];
    }
}

void merge(int* src1, int* src2, int n1, int n2, int* dest){
    // src1, src2 : 정렬된 배열
    // n1, n2 : src1, src2의 길이
    // dest : 결과를 받을 배열

    int p1 = 0; // src1에 접근 시 사용
    int p2 = 0; // src2에 접근 시 사용
    int p = 0;  // dest에 접근 시 사용

    // 합치기
    while(p1 < n1 && p2 < n2){
        if(src1[p1] < src2[p2]){
            dest[p++] = src1[p1++];
        }else{
            dest[p++] = src2[p2++];
        }
    }

    while(p1 < n1){
            dest[p++] = src1[p1++];
    }

    while(p2 < n2){
            dest[p++] = src2[p2++];
    }

}

void mergeSort(int* arr,const int n){
    // arr : 정렬을 수행할 배열
    // n : arr의 크기

    if(n<2) return;

    int* temp = malloc(sizeof(int)*n);
    int h = n/2;

    copy(arr,temp,n);

    mergeSort(temp,h);
    mergeSort(temp+h,n-h);

    //merge
    merge(temp,temp+h,h,n-h,arr);
    free(temp);
}

int main(void){

    int arr0[1]={42};
    printf("arr0\n");
    printf("Before : ");
    printArray(arr0,1);
    mergeSort(arr0,1);
    printf("After  : ");
    printArray(arr0,1);

    int arr1[8]={1,-3,4,2,-1,8,5,3};
    printf("arr1\n");
    printf("Before : ");
    printArray(arr1,8);
    mergeSort(arr1,8);
    printf("After  : ");
    printArray(arr1,8);

    int arr2[11]={3,1,6,9,2,-5,3,6,1,5,-4};
    printf("arr2\n");
    printf("Before : ");
    printArray(arr2,11);
    mergeSort(arr2,11);
    printf("After  : ");
    printArray(arr2,11);

    return 0;
}