Merge Sort

2020-1학기, 대학에서 ‘알고리즘’ 수업을 듣고 공부한 바를 정리한 글입니다. 지적은 언제나 환영입니다 :)

Merge Sort

<정렬>은 알고리즘의 가장 근원이 되는 작업이다. <병합 정렬; Merge Sort>은 <퀵 정렬; Quick Sort>과 함께 인류 역사에서 최고의 알고리즘이라고 생각한다! 👍

Merge Sort는 <분할 정복>을 정말 충실히 수행하는 알고리즘이다.

“split the list into two halves, recursively sort each half, and them merge them.”

Merge Sort는 기능적으로 봤을 때, “Merge Sort“와 “Merge” 두 가지 작업만 수행하면 된다.

function: mergesort($a[1…n]$)

---

if $n > 1$ then
   return merge(mergesort($a[1 … n/2]$), mergesort($a[n/2+1 … n]$))
else
   return $a$
end if

function: merge($x[1…k]$, $y[1…l]$)

---

if $k=0$:   return $y[1…l]$
if $l=0$:   return $x[1…k]$

if $x[1] \le y[1]$ then
   return $x[1]$ $\circ$ merge($x[2…k]$, $y[1…l]$)
else
   return $y[1]$ $\circ$ merge($x[1…k]$, $y[2…l]$)
end if

이번에는 Complexity를 계산해보자. 점화식을 작성하면 아래와 같다.

\[T(n) = 2 \cdot T(n/2) + O(n)\]

고정 비용 $O(n)$는 merge 작업에서 발생하는 비용이다!

$a=2$, $b=2$, $c=1$이므로, $a/b^c = 2/2 = 1$이다. 따라서 <Master Theorem>에 따라

\[O(n) \cdot \log n = O(n \log n)\]

의 Complexity를 가진다!

Merge Sort는 간단하지만 강력하다! 보통 Merge Sort를 직접 구현하는 경우는 드물지만, 어떤 경우에선 Merge Sort의 아이디어를 채용해서 풀어야 한다!

• Skyline Problem

---

Worst-case Analysis

정렬 알고리즘의 절차는 <트리 Tree>의 형태로 표현할 수 있다. 예를 들어 아래의 트리는 $a_1$, $a_2$, $a_3$ 세 개의 원소에 대한 정렬을 도식화한 그림이다.

위와 같이 주어진 배열에 대해 원소를 비교하는 모든 경우를 고려하게 되면, 우리는 배열의 $n$개 원소에 대한 가능한 모든 <순열 Permutation>을 확인하는 것과 동일하다. 즉, $n!$ 가짓수의 가능한 순서를 생각한다는 말이다. 이때, “정렬”이라는 작업은 <비교 트리; Comparison Tree>에서 가능한 하나의 <경로 Path>를 취하는 것이라고 할 수 있다.

비교 트리에서 가장 긴 경로(longest path)의 길이를 생각해보자. 비교 트리는 총 $n!$개 만큼의 leaf node를 가지므로 트리의 깊이(depth)는 $\log {(n!)}$이 된다. 이 트리의 “깊이”는 곧 Worst-case에서의 비교 횟수이다!!

약간의 정리들을 활용하면, $\log {(n!)}$에 대해 아래가 성립함을 보일 수 있다.

\[\log {(n!)} \ge c \cdot n \log n \quad \textrm{for some} \; c > 0\]

이것은 함수 $\log {(n!)}$에 대해 $\Omega \left( n \log {n} \right)$임을 의미한다. 그리고 어떤 정렬 알고리즘도 $n$개 원소를 정렬하는 데에 $\Omega (n \log {n})$ 만큼의 비교는 반드시 수행해야 함을 의미한다. 즉, 정렬 알고리즘이 가질 수 있는 Complexity의 하한선이 $n \log {n}$이라는 의미이다.

그런데 우리는 윗 문단에서 <Master Theorem>으로 Merge Sort가 $O(n \log {n})$의 Complexity를 가진다는 걸 유도했다. 즉, Merge Sort의 Complexity가 $n \log {n}$ 보다 절대 높아지지 않는다는 거다! 이 말은 곧 $O(n \log {n})$의 효율을 갖는 Merge Sort가 optimal 정렬 방식이라는 것을 말한다!! $\blacksquare$

p.s. 본인도 처음에는 이해가 잘 되질 않았다. 아마 $\Omega (n \log {n})$의 의미가 잘 와닿지 않았던 것 같은데, 본인은 $\Omega (n \log {n})$를 Complextiy의 하한선이라고 해석했다. 즉, 정렬 알고리즘이 $\Omega (n \log {n})$의 Complexity를 갖는다는 건 모든 정렬 알고리즘은 $n \log {n}$ 보다 크거나 같은 Complexity를 가질 수 밖에 없다고 해석했다는 말이다. 그런데 Merge Sort는 $O(n \log {n})$의 Complextiy를 가지니, 절대 $n \log {n}$ 이상으로는 Complexity가 커지지 않는다. 그러니 $O(n \log {n)}$은 $\Omega(n \log {n)}$ 아래에서 optimal 일 수 밖에 없다!

---

Merge Sort - Code

아래 코드는 본인 스타일 대로 구현한 Merge Sort 코드다. 원래는 배열을 사용해 in_place로 구현해보려고 했는데, 뭔가 코드가 예쁘게 나오지 않을 것 같아서 vector STL과 in_place가 아닌 방식으로 구현해봤다.

vector<int> merge(vector<int> left, vector<int> right) {
  int left_idx = 0, right_idx = 0;

  vector<int> sorted;

  while((left_idx < left.size()) && (right_idx < right.size())) {
    if (left[left_idx] <= right[right_idx]) {
      sorted.push_back(left[left_idx]);
      left_idx += 1;
    } else {
      sorted.push_back(right[right_idx]);
      right_idx += 1;
    }
  }

  for (int i = left_idx; i < left.size(); i++) {
    sorted.push_back(left[i]);
  }

  for (int i = right_idx; i < right.size(); i++) {
    sorted.push_back(right[i]);
  }

  return sorted;

}

vector<int> mergeSort(vector<int> arr) {
  if (arr.size() <= 1) {
    return arr;
  }
  int mid = arr.size() / 2;
  vector<int> leftSide = mergeSort(vector<int>(arr.begin(), arr.begin() + mid));
  vector<int> rightSide = mergeSort(vector<int>(arr.begin() + mid, arr.end()));

  return merge(leftSide, rightSide);
}

개인적인 경험으론 MergeSort는 python으로 구현하는게 가장 쉽고 편하다!