[Programming/Algorithm] 병합 정렬(Merge Sort)

병합 정렬은 '분할 정복(divide and conquer)'이라는 알고리즘 디자인 기법에 근거하여 만들어진 정렬 방법이다. 

분할 정복이란, 말 그대로 복잡한 문제를 복잡하지 않은 문제로 '분할(divide)'하여 '정보(conquer)'하는 방법을 말한다. 단 분할해서 정복했으니 정복한 후에는 '결합(combine)'의 과정을 거쳐야 한다. 즉 다음 3단계를 거치도록 알고리즘을 디자인 하는 것이 분할 정복법이다.

• 1단계 분할(Divide) : 해결이 용이한 단계까지 문제를 분할해 나간다.
• 2단계 정복(Conquer) : 해결이 용이한 수준까지 분할된 문제를 해결한다.
• 3단계 결합(Combine) : 분할해서 해결한 결과를 결합하여 마무리한다.

이 방법을 근거로 어떻게 병합 정렬 알고리즘이 디자인되었을까? 기본 원리는 다음과 같다.

8개의 데이터를 동시에 정렬하는 것보다, 이를 둘로 나눠서 4개의 데이터를 정렬하는 것이 쉽고, 또 이들 각각을 다시 한번 둘로 나눠서 2개의 데이터를 정렬하는 것이 더 쉽다.

병합 정렬의 기본 원리

위 그림에서는 오름차순 정렬을 기준으로 변합 정렬의 기본 원리를 설명하고 있다. 그래서 8개의 데이터를 둘로 나눈 것이 전부이지만, 실제로는 훨씬 더 작게 분할을 해야 한다.

병합 정렬은 데이터가 1개만 남을 때까지 분할을 해나간다. 데이터가 2개만 남아도 정렬을 할 필요가 있지만, 데이터가 1개만 남으면 그 조차도 불필요해지기 때문이다.

언뜻 보면 병합 정렬은 나누는 것이 핵심인 것처럼 보인다. 하지만 실제 정렬은 나눈 것을 병합하는 과정에서 이뤄진다. 그래서 이름이 '병합 정렬'인 것이다.

병합 정렬의 예

위 그림에서 보이듯이 우선은 분할의 과정을 거친다. 전체 데이터를 둘로 나누는 과정을, 데이터가 하나씩 구분이 될 때까지 진행을 한다. 위에서는 총 8개의 데이터가 존재하므로 둘로 나누는 과정을 3회 진행하면 데이터가 하나씩 구분이 된다. 이렇듯 분할을 할 때에는 정렬을 고려하지 않고 그저 분할만 하면 된다.

분할이 완료되었다면 이제 병합을 진행할 차례이다. 위 그림에서 보이듯이, 우선 나뉘었던 둘을 하나로 묶는다. 8과 2개 원래 하나였으니, 이 둘을 하나로 묶는다. 단, 그냥 묶는 것이 아니라 정렬순서를 고려해서 묶는다. 이렇듯 분할이 총 3회 진행되었으니, 묶는 과정도 총 3회에 걸쳐 진행된다. 그리고 그 결과 정렬이 완료된다.

void MergeSort(int arr[], int left, int right);

첫 번째 인자로 정렬대상이 감긴 배열의 주소 값을 전달하고, 두 번째 인자와 세 번째 인자로 정렬대상의 범위정보를 인덱스 값의 형태로 전달한다. 

대략적인 MergeSort 함수는 다음과 같다.

void MergeSort(int arr[], int left, int right) {
  int mid;
  
  // left가 작다는 것은 더 나눌 수 있다는 뜻
  if(left < right) {
    // 중간지점 계산
    mid = (left + right) / 2;
    
    // 둘로 나눠서 각각을 정렬
    MergeSort(arr, left, mid);
    MergeSort(arr, mid+1, right);
    
    // 정렬된 두 배열을 병합
    MergeTwoArea(arr, left, mid, right);
  }
}

MergeSort함수는 위에서 보인 그림의 내용을 그대로 구현한 결과이다. 다만 재귀적으로 구현하여, 데이터가 하나씩 구분이 될 때까지 쪼개서 MergeSort 함수를 호출하도록 정의했을 뿐이다.

MergeTwoArea(arr, left, mid, right);

위의 함수는 MergeSort 함수호출의 결과로 정렬된 두 영역을 하나로 묶기 위한 함수 호출이다. 따라서 위의 문장이 의미하는 바는 다음과 같이 이해할 수 있다.

배열 arr의 left ~ mid까지, 그리고 mid+1 ~ right까지 각각 정렬이 되어 있으니, 이를 하나의 정렬 된 상태로 묶어서 배열 arr에 저장해라.

#include <iostream>

using std::cout;
using std::cin;
using std::endl;


void MergeTwoArea(int arr[], int left, int mid, int right) {
    int fIdx = left;
    int rIdx = mid + 1;

    // 병합 한 결과를 담을 배열 sortArr 동적 할당
    int* sortArr = new int[sizeof(int) * (right + 1)];
    int sIdx = left;

    // 병합 할 두 영역의 데이터들을 비교하여, 정렬 순서대로 sortArr에 하나씩 옮김
    while (fIdx <= mid && rIdx <= right) {
        if (arr[fIdx] <= arr[rIdx]) {
            sortArr[sIdx] = arr[fIdx++];
        }
        else {
            sortArr[sIdx] = arr[rIdx++];
        }
        sIdx++;
    }

    // 배열의 앞부분이 모두 sortArr에 옮겨졌다면,
    // 배열의 뒷부분에 남은 데이터들을 sortArr에 그대로 옮김
    if (fIdx > mid) {
        for (int i = rIdx; i <= right; i++, sIdx++) {
            sortArr[sIdx] = arr[i];
        }
    }
    // 배열의 뒷부분이 모두 sortArr에 옮겨졌다면,
    // 배열의 앞부분에 남은 데이터들을 sortArr에 그대로 옮긴다.
    else {
        for (int i = fIdx; i <= mid; i++, sIdx++) {
            sortArr[sIdx] = arr[i];
        }
    }

    for (int i = left; i <= right; i++) {
        arr[i] = sortArr[i];
    }

    delete[] sortArr;
}


void MergeSort(int arr[], int left, int right) {
    int mid;

    if (left < right) {
        // 중간 지점을 계산
        mid = (left + right) / 2;

        // 둘로 나눠 각각을 정렬
        MergeSort(arr, left, mid);
        MergeSort(arr, mid + 1, right);

        // 정렬된 두 배열을 병합
        MergeTwoArea(arr, left, mid, right);
    }
}


int main() {
    int arr[] = { 4, 2, 1, 3, 5, 7, 6 };
    int n = sizeof(arr) / sizeof(int);

    MergeSort(arr, 0, n-1);

    for (int i = 0; i < n; i++) {
        cout << arr[i] << ' ';
    }
    cout << endl;

    return 0;
}


/* 결과

1 2 3 4 5 6 7

*/

MergeTwoArea 함수 구현이 간단치 않다. 먼저 위 함수에 삽입된 while문의 반복조건을 이해해야 한다.

while(fIdx <= mid && rIdx <= right) {
  ...
}

위의 while문에서 보이는 fIdx와 rIdx에는 각각 병합할 두 영역의 첫 번째 위치정보가 담긴다. 위치정보는 인덱스 값이다. 그리고 이 두 변수의 값을 증가시켜 가면서 두 영역의 데이터들을 비교해 나가게 된다. 

병합할 두 영역이라는 것이 하나의 배열 안에 함께 존재한다. 따라서 fIdx는 배열의 앞쪽 영역을 가리키게 되고, rIdx는 배열의 뒤쪽 영역을 가리키게 되는데, 배열의 앞과 뒤를 구분하는 기준은 변수 mid에 저장되어 있다. mid + 1의 위치에서부터 뒤쪽 영역이 시작되기 때문이다.

초기 상태

위의 그림은 두 영역을 합치기 직전의 상태를 보여준다. fIdx와 rIdx가 가리키는 위치에 집중하자. 이 둘에 저장된 값은 하나씩 증가하면서 다음과 같이 값의 비교를 진행하게 된다.

• 2와 1 비교 : 비교연산 후 1을 sortArr로 이동, 그리고 rIdx의 값 1 증가
• 2와 4 비교 : 비교연산 후 2를 sortArr로 이동, 그리고 fIdx의 값 1 증가
• 3과 4 비교 : 비교연산 후 3을 sortArr로 이동, 그리고 fIdx의 값 1 증가
• 7과 4 비교 : 비교연산 후 4를 sortArr로 이동, 그리고 rIdx의 값 1 증가
• 7과 5 비교 : 비교연산 후 5를 sortArr로 이동, 그리고 rIdx의 값 1 증가
• 7과 6 비교 : 비교연산 후 6을 sortArr로 이동, 그리고 rIdx의 값 1 증가

이러한 과정을 거쳐서 마지막으로 7과 6의 비교가 끝나면, 다음 그림에서 보이듯이 rIdx는 right를 넘어서는 위치를 가리키게 되어 더 이상의 비교가 무의미하게 된다.

비교 완료 상태

이렇듯 두 영역을 비교하다 보면, 한 영역의 데이터들이 모두 옮겨져서 더 이상 비교가 불가능한 상황에 이르게 된다. 위 그림에서 보이듯이 rIdx가 right보다 커지는 경우는 배열의 뒤쪽 영역의 데이터들이 모두 옮겨진 상황이다. 유사하게 fIdx가 mid보다 커지는 경우는 배열의 앞쪽 영역의 데이터들이 모두 옮겨진 상황이다. 따라서 다음 while문의 반복 조건이 의미하는 바는 다음과 같다.

while(fIdx <= mix && rIdx <= right) { ... }

이는 배열의 앞쪽 영역에도, 배열의 뒤쪽 영역에도 비교의 대상이 남아있는 상황에서 반복조건이 '참'임을 의미한다. 그리고 위의 while문을 빠져 나온 뒤에 할 일은, 어느 영역의 데이터가 남아 있는지 확인하여 이를 그래도 옮기면 된다. 남아 있는 데이터들은 정렬의 우선순위가 낮은 데이터들이기 때문이다. 그래서 다음과 같이 if~else 문이 등장하는 것이다.

if(fIdx > mid) // 배열의 앞부분이 모두 sortArr에 옮겨졌다면,
{
  // 배열의 뒷부분에 남은 데이터들을 sortArr에 그대로 옮긴다.
}
else // 배열의 뒷부분이 모두 sortArr에 옮겨졌다면,
{
  // 배열의 앞부분에 남은 데이터들을 sortArr에 그대로 옮긴다.
}

---

병합 정렬(Merge Sort) : 성능평가

병합 정렬의 성능평가를 위해 비교연산의 횟수와 이동연산의 횟수를 계산해보자. 그런데 병합 정렬의 성능은 MergeSort 함수가 아닌, MergeTwoArea 함수를 기준으로 계산해야 한다. 왜냐하면 비교연산과 이동연산이 실제 정렬을 진행하는 MergeTwoArea 함수를 중심으로 진행되기 때문이다.

while(fIdx <= mid && rIdx <= right) {
  if(arr[fIdx] <= arr[rIdx]) {    // 핵심이 되는 비교 연산
    sortArr[sIdx] = arr[fIdx++];
  }
  else {
    sortArr[sIdx] = arr[rIdx++];
  }
  sIdx++;
}

정렬의 우선순위를 비교하는 비교연산이 중심이므로, 위에서 핵심이라고 지적한 비교연산을 중심으로 비교연산의 횟수를 계산하면 된다.

하나와 하나가 모여 둘이 될 때, 비교연산은 최대 2회 진행이 된다. 예를 들어 8과 2를 하나로 뭉친다고 가정해 보자. 그러면 8과 2를 비교해야 한다. 바로 앞서 핵심이라고 지적한 비교연산이 일때 일어난다.

그리고 둘과 둘이 모여 넷이 될 때, 최대 비교연산의 횟수는 최악의 경우 4회이다. 예를 들어 1과 5, 그리고 4와 6을 하나의 덩어리로 뭉치는 경우를 생각해보자. 이 경우 다음과 같이 비교가 진행된다.

• 1과 4를 대상으로 비교연산 후 1을 sortArr로 이동
• 5와 4를 대상으로 비교연산 후 4를 sortArr로 이동
• 5와 6을 대상으로 비교연산 후 5를 srotArr로 이동
• 마지막으로 남은 6을 sortArr로 이동하기 위한 if~else문에서의 비교 연산

이렇듯 마지막에 하나의 데이터가 남을 때까지 비교연산이 진행되는 경우에 비교연산의 횟수는 최대가 되며 그 수는 4이다. 이것을 정리하면 다음과 같이 표현할 수 있다.

정렬의 대상인 데이터의 수가 n개 일 때, 각 병합의 단계마다 최대 n번의 비교연산이 진행된다.

따라서 데이터의 수가 n개 일 때, 병합 정렬에서 진행되는 최대 비교연산의 횟수는 다음과 같다.

nlog2n

위의 식에서 logn2이 나온 이유는? 데이터의 수가 8개 일 때 병합의 과정은 3회 진행이 되었다. 마찬가지로 데이터의 수가 16개 일 때 병합의 과정은 4회 진행이 된다. 즉, 데이터의 수 n과 그에 따른 병합 과정의 횟수 k에는 다음 식이 성립한다.

k = log2n

따라서 병합 정렬의 비교연산에 대한 빅-오는 다음과 같다.

O(nlog2n)

이번에는 이동연산에 대해 살펴보자. 이동연산의 관점에서 MergeTwoArea 함수를 정리하면 다음과 같다.

void MergeTwoArea(int arr[], int left, int mid, int right) {
  ...
  // 임시 배열
  int* sortArr = (int*)malloc(sizeof(int) * sizeof(right + 1));
  ...
  
  while(fIdx <= mid && rIdx <= right) {
    // 배열 sortArr에 데이터를 정렬하며 이동
  }
  
  if(fIdx > mid) {
    // 배열 sortArr에 나머지 데이터 이동
  }
  else {
    // 배열 sortArr에 나머지 데이터 이동
  }
  
  // 임시 배열에 저장된 데이터 전부를 이동
  for(int i=left; i<=right; i++) {
    arr[i] = sortArr[i];
    ...
  }
}

위의 코드를 보면 데이터의 이동이 발생하는 이유 두 가지가 다음과 같음을 알 수 있다.

• 임시 배열에 데이터를 병합하는 과정에서 한 번
• 임시 배열에 저장된 데이터 전부를 원위치로 옮기는 과정에서 한 번

즉, 각각의 상황에서 비교연산 횟수의 두 배에 해당하는 이동연산이 이뤄진다. 따라서 병합 정렬의 이동연산 횟수는 최악, 평균, 최선의 경우에 상관없이 다음과 같다.

2nlog2n

하지만 빅-오에서 숫자 2는 무시할 수 있으므로, 병합 정렬의 이동연산에 대한 빅-오는 다음과 같다.

O(nlog2n)

즉, 병합 정렬의 비교연산과 이동연산의 빅-오는 nlog2n으로 정리가 된다.

참고로 병합 정렬에는 임시 메모리가 필요하다는 단점이 있다. 하지만 이는 정렬의 대상이 배열이 아닌 연결 리스트일 경우 단점이 되지 않기 때문에, 연결 리스트의 경우에는 병합 정렬에서 그만큼 더 좋은 성능을 기대할 수 있다.