병합정렬

시간복잡도가 O(nlogn) 인 정렬 알고리즘이다.

divide & conquer 의 대표적인 예라 볼 수 있다.

 

동작방식은 아래를 재귀적으로 한다.

1. 배열을 절반으로 분할 한다.

2. 분할 된 배열을 병합한다. 

 

void merge_sort(int * arr, int len)
{
    if (len <= 1) //재귀 탈출 조건
        return;
    
    int div_len = len / 2;
    merge_sort(arr, div_len);
    merge_sort(arr + div_len, len - div_len);
    merge(arr, div_len, arr + div_len, len - div_len);
}

void merge(int * arr1, int len1, int * arr2, int len2) //두 인덱스 모두 존재 할 때 까지
{
    int * arr = new int[len1 + len2];
    int idx = 0, idx1 = 0, idx2 = 0;
    
    for ( ; idx1 < len1 && idx2 < len2; idx++)
    {
        if (arr1[idx1] <= arr2[idx2])
            arr[idx] = arr1[idx1++];
        else
            arr[idx] = arr2[idx2++];
    }
    
    for ( ; idx1 < len1; idx1++) //arr1에 인덱스가 남아 있다면
        arr[idx++] = arr1[idx1];
    for ( ; idx2 < len2; idx2++) //arr2에 인덱스가 남아 있다면
        arr[idx++] = arr[idx2];
    
    for (idx = 0; idx < len1 + len2; idx++) //원래 배열에 정렬된 정보를 복사시킴
        arr1[idx] = arr[idx];
        
    delete [] arr;
}

분할은 더 이상 배열을 나눌 수 없을 때 까지 반복하는 것이다. 

그래서 중요한 것은 병합하는 것이다.

 

arr : 5, 4, 3, 2, 1 이 있을 때

 

1) merge_sort(arr, 2) : {5, 4} | 3, 2, 1

-> merge_sort(arr, 1) & merge_sort(arr + 1, 1)

-> merge

-> arr1 = {5} & arr2 = {4} -> arr[] = {4, 5} -> arr1[] = {4, 5}, 여기서 arr1 == arr

 

2) merge_sort(arr + 3, 3) : 4, 5 | {3, 2, 1}

->merge_sort(arr + 2, 1) & merge_sort(arr + 2 + 1, 2)

                                          -> merge_sort(arr + 2 + 1, 1) & merge_sort(arr + 2 + 1 + 1, 1)

                                          -> merge

                                          -> arr1 = {2} & arr2 = {1} -> arr[] = {1, 2} -> arr1[] = {1, 2}

->merge

->arr1 = {3} & arr2 = {1, 2} -> arr[] = {1, 2, 3} -> arr1[] = {1, 2, 3}, 여기서 arr1 == arr + 3

 

3)merge

->arr1 = {4, 5} && arr2 = {1, 2, 3} -> arr[] = {1, 2, 3, 4, 5} -> arr1[] = {1, 2, 3, 4, 5}, 여기서 arr1 == arr

 

그래서 {1, 2, 3, 4, 5}로 정렬이 된다.

 

정렬을 위해 추가 메모리 공간이 필요하다. in-place 한 정렬이 아니다.

또한 들어온 순서를 유지해서 정렬 할 수 있다.