병합 정렬(Merge Sort)

이 글은 Divide & Conquer(분할 정복 기법)을 알고 계신다는 가정 하에 작성되었습니다. 분할 정복에 대한 글은 제가 저번에 쓴 글을 참고하셔도 됩니다. 2022.10.17 - [개념 정리/알고리즘] - 분할 정복 기법(Divide & Conquer)

병합 정렬(Merge Sort)

병합 정렬을 하는 과정을 분할 정복 기법을 사용해서 설명할 수 있습니다.

1. 전체 배열을 반씩 나눕니다(Divide). 이 과정은 재귀적으로 진행됩니다.
2. 반씩 나눈 배열들을 정렬합니다(Conquer).
3. 정렬한 배열들을 다시 하나로 합칩니다(Combine).

여기서의 base case는 배열의 길이가 1인 경우입니다. 배열의 길이가 1이면 이 자체로 정렬이 되어있기 때문에 배열의 길이가 1이면 반씩 나누는 것을 그만둡니다.

정렬 과정

길이가 4인 정수형 배열 {3, 2, 3, 4}를 정렬해봅시다. 정렬의 과정을 좀 더 잘 보이게 하기 위해 하나의 3에 '*' 표시를 했습니다.
먼저 배열을 반씩 계속 나눠갈 것입니다. 나눠진 배열의 길이가 1이면 나누는 작업을 종료합니다.

배열을 재귀적으로 절반씩 나눕니다.

절반씩 나누는 과정을 C++ 코드로 작성하면 아래와 같습니다.

void mergeSort(int* numArray, int start, int end)    
{
    // start: 배열의 시작 인덱스, end: 배열의 끝 인덱스
    if (start < end)
    {
        int mid = (start + end) / 2;
        mergeSort(numArray, start, mid);    // 왼쪽 절반
        mergeSort(numArray, mid + 1, end);    // 오른쪽 절반
        
        // 이 이후로는 merge 과정 진행
    }
}

그 후로 나눠진 배열들을 정렬시키면서 합칩니다.
(2022.10.23 일요일 그림 삭제)
병합 정렬에서 핵심 연산이 진행되는 구간이 위의 그림에서 Merge라고 표현한 부분입니다. 두 배열의 원소들을 하나씩 비교하면서 작은 값부터 정렬합니다. 이를 그림으로 그려보면 아래와 같습니다.

merge 과정 1

merge 과정 2

left와 right을 움직이면서 각각 가리키는 값끼리의 비교 연산을 진행합니다. 비교 결과를 원래 배열에 반영해줍니다. 이 과정을 C++ 코드로 작성하면 아래와 같습니다.

// 위의 코드 블럭에서 이어서

int tmp[_MAX_LENGTH_] = {0};    // 여기서 _MAX_LENGTH_를 4라고 가정
for (int i = start; i <= end; i++) { tmp[i] = *(numArray + i); }

int leftPtr, rightPtr, originPtr;    // originPtr: 원래 배열에다 갱신할 위치
leftPtr = originPtr = start;
rightPtr = mid + 1;

while (leftPtr <= mid && rightPtr <= end)
{
    if (tmp[leftPtr] < tmp[rightPtr]) { numArray[originPtr++] = tmp[leftPtr++]; }
    else { numArray[originPtr++] = tmp[rightPtr++]; }
}
while (leftPtr <= mid) { numArray[originPtr++] = tmp[leftPtr++]; }
while (rightPtr <= end) { numArray[originPtr++] = tmp[rightPtr++]; }

따라서 병합 정렬의 전체 코드는 아래와 같습니다.

void mergeSort(int* numArray, int start, int end)
{
    if (start < end)
    {
        int mid = (start + end) / 2;
        mergeSort(numArray, start, mid);
        mergeSort(numArray, mid + 1, end);

        int tmp[_MAX_LENGTH_] = {0};
        for (int i = start; i <= end; i++) { tmp[i] = *(numArray + i); }

        int leftPtr, rightPtr, originPtr;
        leftPtr = originPtr = start;
        rightPtr = mid + 1;

        while (leftPtr <= mid && rightPtr <= end)
        {
            // if문의 비교가 basic operation
            if (tmp[leftPtr] < tmp[rightPtr]) { numArray[originPtr++] = tmp[leftPtr++]; }
            else { numArray[originPtr++] = tmp[rightPtr++]; }
        }
        while (leftPtr <= mid) { numArray[originPtr++] = tmp[leftPtr++]; }
        while (rightPtr <= end) { numArray[originPtr++] = tmp[rightPtr++]; }
    }

이번에는 그동안 적어왔던 다른 정렬 방법들과 다르게 tmp 배열을 함수 내에서 사용합니다. tmp 배열의 길이는 정렬할 배열의 원소의 수에 따라 달라질 것입니다. 따라서 이 알고리즘의 메모리 복잡도는 O(n)이라고 할 수 있습니다. 정렬 과정 중 배열의 원소들을 tmp에 옮기는 과정이 존재하므로 In-place가 아닌 알고리즘이고, 위의 예시에서와 같이 같은 숫자가 정렬 후 순서가 보장되므로 stable 한 알고리즘입니다.

병합 정렬의 시간 복잡도

이번에는 시간 복잡도를 점화식을 풀어서 찾아보겠습니다.
Basic operation을 원소들의 크기를 비교하는 비교 연산이라고 할 때 길이가 n인 배열에서 실행된 basic operation 횟수를 T(n)이라고 합시다. 그러면 T(n)은 아래와 같이 정의됩니다.
$$ T(n) = \left\{\begin{array}{cc} 0 \quad (n = 1)
\\T(\left \lfloor n / 2 \right \rfloor) + T(\left \lceil n / 2 \right \rceil) + (n - 1) \quad (n > 1)
\end{array}\right. $$
길이가 1이면 비교 연산은 진행되지 않습니다. 길이가 1보다 크면 절반에서 비교가 일어난 횟수와 다른 절반에서 일어난 비교 횟수, 그리고 두 배열의 원소들을 보면서 진행하는 비교 횟수(최대 n - 1)까지 합쳐야 합니다.
n이 2의 제곱수인 경우, n > 1일 때의 식을 간단하게 2 * T(n / 2) + n이라 표현할 수 있습니다. 이 식을 풀어봅시다.

2 * T(n / 2) + n = 2 * {2 * T(n / 4) + n / 2} + n
= 4 * T(n / 4) + 2n = 4 * {2 * T(n / 8) + n / 4} + 2n
= 8 * T(n / 8) + 3n = 8 * {2 * T(n / 16) + n / 8} + 3n
...
= n * T(1) + (log n) * n (밑이 2인 log)
= n log n

따라서 병합 정렬의 시간 복잡도는 O(nlogn)입니다.