합병 정렬 (Merge Sort)

합병 정렬 (Merge Sort)

• 입력이 2개의 부분문제로 분할되고, 부분문제의 크기가 1/2로 감소하는 분할 정복 알고리즘
• 연결 리스트에 있는 데이터를 정렬할 때 퀵 정렬이나 힙 정렬보다 훨씬 효율적이라고 한다.

  MergeSort(int arr[], int p, int q)
  {
    if (p < q)
    {
      int k = (p + q) / 2;
      MergeSort(arr, p, k);
      MergeSort(arr, k + 1, q);
      arr[p] ~ arr[k]와 arr[k + 1] ~ arr[q]를 합병한다.
    }
  }

  
• pseudo code

---

시간 복잡도

• 분할하는 부분
  • 배열의 중간 인덱스 계산과 재귀 호출 2번으로 O(1) 시간이 걸린다.
• 합병하는 부분
  • 두 정렬된 배열 A, B의 크기가 각각 n과 m이고 이를 합병하여 새로운 배열 C를 만드는 부분
    • (n + m - 1)번의 비교를 통해 배열 C를 채우므로 시간 복잡도는 O(n + m)이다.
  • 층 별 비교
    • 각 층에서 수행되는 비교 횟수는 분할된 크기 * 분할된 개수로, 항상 O(n)이다.
    • 층 수는 log₂n이다.
    • 즉, 모든 층에서 수행되는 비교 횟수는 O(nlog₂n)이다.
  • 각 층에서 비교 후에 새로운 배열로 이동시키는 과정의 시간복잡도는 O(nlog₂n)이다.
• 모두 더하면 O(nlog₂n)이다.

---

공간 복잡도

• 입력과 같은 크기의 공간이 별도로 필요하므로 O(n)이다.

---

C++ 코드

#include <iostream>
#include <vector>

void PrintElements(const std::vector<int>& arr)
{
    for (const auto& e : arr)
        std::cout << e << " ";
    std::cout << std::endl;
}

void Merge(std::vector<int>& arr, int low, int mid, int high)
{
    int i = low;
    int j = mid + 1;
    int temp_idx = low;
    static std::vector<int> temp(arr);

    while ((i <= mid) && (j <= high))
    {
        if (arr[i] < arr[j])
            temp[temp_idx++] = arr[i++];
        else
            temp[temp_idx++] = arr[j++];
    }
    while (i <= mid)
        temp[temp_idx++] = arr[i++];
    while (j <= high)
        temp[temp_idx++] = arr[j++];

    while (low <= high)
    {
        arr[low] = temp[low];
        low++;
    }
}

void MergeSort(std::vector<int>& arr, int low, int high)
{
    if (low == high)
        return ;

    int mid = (low + high) / 2;

    MergeSort(arr, low, mid);
    MergeSort(arr, mid + 1, high);
    Merge(arr, low, mid, high);
}

int main()
{
    using namespace std;

    vector<int> arr = { 37, 10, 22, 30, 35, 13, 25, 24 };

    PrintElements(arr);
    MergeSort(arr, 0, arr.size() - 1);
    PrintElements(arr);
}

/* stdout
37 10 22 30 35 13 25 24 
10 13 22 24 25 30 35 37
*/

---

참고

• 알기쉬운 알고리즘 (양성봉 저, 생능 출판)