[알고리즘] 병합 정렬(Merge Sort)

병합 정렬은 재귀적으로 배열을 분할하여 정렬하고 다시 합병한다. 이를 분할과 정복 패러다임이라고 한다.

분할과 정복

분할과 정복 패러다임은 다음의 세 단계로 이루어진 일반적인 용어로 설명될 수 있다.

분할(Divide): 입력의 크기가 특정한 임계값보다 작다면 간단한 메소드를 사용하여 직접 문제를 풀고, 얻어진 답을 반환한다. 그렇지 않으면, 입력 데이터를 둘 이상의 분리된 부분 집합으로 분할한다.
재귀(Recur): 부분 집합에 연관된 부분 문제를 재귀적으로 푼다.
정복(Conquer): 부분 문제에 대한 답을 구해 본래 문제의 답으로 병합한다.

C++ 구현

template <class RandomIt>
void merge_sort(RandomIt first, RandomIt last)
{
    if (first + 1 == last) return;
    RandomIt mid = first + (last-first)/2;
    merge_sort(first, mid);
    merge_sort(mid, last);
    for (RandomIt a = first, b = mid; a != b; ++a)
        if (*a > *b)
        {
            RandomIt c = ++b;
            while(*--c < *(c-1))
            {
                auto temp = *c;
                *c = *(c-1);
                *(c-1) = temp;
            }
        }
}

[first, last) 범위의 원소를 오름차순으로 병합 정렬하는 코드이다.