2025-03-17發表2025-03-18更新演算法學習筆記8 分鐘讀完 (大約1219個字)

Merge Sort

題目

合併排序 Merge Sort，經典排序之一。將給定一串數字排序，時間複雜度的要求為 O(nlogn)。

解題

Merge Sort 主要實做的觀念是 Divide and conquer，切大目標為小目標，小到不能再小之後再合併結果，因此通常用遞迴去處理。

如果我們來排序 [1,3,4,2] 這個 Array，透過 Merge Sort 會先將其中間切一刀，分成 [1,3] 及 [4,2]。[1,3] 會被分成 [1] 及 [3]，而 [4,2] 會被分成 [4] 及 [2]。

都被分成不能再分的時候，合併起來：將 [1] 及 [3] 合併成 [1,3]，[4] 及 [2] 合併成 [2,4]，也就是說合併完成後的每個單位都是排序完的，而最終得到 [1,2,3,4]。

晚一點再看「合併」這件事是怎麼做的，先來看看整個合併排序的遞迴是怎麼切分的，既然是遞迴，就能畫出一棵 Recursive Tree。

Recursive Tree

以下就是整個遞迴的呼叫過程

    1,3,4,2
   /       \
  1,3     4,2    --> 切一刀一分為二
 /   \   /   \
1     3 4     2  --> 二分為四
 \   /   \   /
  1,3     2,4    --> 合併
   \       /
    1,2,3,4      --> 再合併

那麼程式要怎麼呼叫呢？大致上會長成下面這段 snippet

mergeSort(arr) {
  if arr's length == 1: return arr;
  leftArr = mergeSort(leftHalfArr);
  rightArr = mergeSort(rightHalArr);
  resultArr = merge(leftArr, rightArr); // Merge left and right array
  return resultArr;
}

中間切一刀，然後左半部做一遍 mergeSort，右半部做一遍 mergeSort，把兩邊結果 merge 起來，就完成了。

Merge function

那 Merge 要怎麼做把兩個排序過的 Array 整合起來呢？例如將 [1,3] 和 [2,4] 整合起來。

首先就這兩個 Array 本質上是 in-memory 的，會在原本的 Array 上已經被排好序了，所以目前的 Array 會長成 [1,3,2,4]，然後我們有的參數是左 Array 的開始 Index，右邊 Array 的開始 Index 以及最後元素在哪。

1
2
3

[  1  3  2  4  ]
   ^     ^    ^- end
start    mid

例如這樣，start 在 Index 0，mid 在 Index 2， end 在 Index 3，所以在合併之前不需要額外的記憶體空間去儲存。

但，合併時就需要了，否則就得用時間換取空間。以這 4 個元素的合併來說，我們就需要長度為 4 的額外 Array 來暫存。將準備被合併的兩個 Array 比較大小，較小的放進 Temp Array 中，補滿為止。

1  3  2  4  | Temp Array []
i     j     | Temp Array [1]        1 < 2, Put 1
   i  j     | Temp Array [1,2]      2 < 3, Put 2
   i     j  | Temp Array [1,2,3]    3 < 4, Put 3
      i     | Temp Array [1,2,3,4]  i out of range, put 4
      i    j| Temp Array [1,2,3,4]  j out of range

原理就是雙指針指向兩份要合併的 Array，誰比較小就丟誰進 Temp Array，然後移動指針，直到超出邊界。最後再將原本的 Temp Array 丟回原 Array 即可。

Time Complexity

Merge Sort 的 Time Complexity 是 O(nlogn)，要怎麼計算稍嫌複雜，我們可以從 Recursive tree 看起。

    1,3,4,2      --> 跑 1 次
   /       \
  1,3     4,2    --> 跑 2 次（找 2 次中間點）
 /   \   /   \
1     3 4     2  --> 跑 4 次（找 4 次中間點）
|     | |     |  ----------------------  上面是切分（ n ），下面是合併（ nlogn ）
1     3 4     2  --> 跑 1+1+1+1 也就是 n
 \   /   \   /
  1,3     2,4    --> 跑 2+2     也就是 n
   \       /
    1,2,3,4      --> 跑 4       也就是 n

切分時，每次就是找個中間點切兩邊往下傳，不需走訪所有元素，所以複雜度是 1 + 2 + 4 + ... + n（加了樹的高度 log(n) 層），等同於 2n - 1，可以簡化成時間複雜度的表達式 O(n)。

真正花時間的是在後續合併時，每次合併都會需要走訪所有的 n 個元素，並且需要合併 log(n) 次，因次在這個階段的時間複雜度為 O(nlogn)。

切分和合併的複雜度為 O(n) + O(nlogn)，前者量級較小可忽略不計，也就是說整個合併排序的時間複雜度為 O(nlogn)。

Space Complexity

Merge Sort 在合併的階段才會用到額外的空間，來暫時儲存左右 Array 合併的結果，我們只需要建立一個長度為 n 的 Array，在每次合併時使用這個空間即可，因此需要用到 O(n) 的時間複雜度。

總結

Merge Sort 是蠻經典的排序演算法，但在實務上其他演算法，如 Quick Sort 有更好的效率。雖然複雜度一樣，但是工程上可以快個常數倍就非常值得使用了。

然而在一些情況下，Merge Sort 還是有其優勢，例如其穩定性就比較好，每次都是一分為二，不會像 Quick Sort 在極端情況可能會退化成 O(n^2) 的時間複雜度。尤其是在排序 Linked List 的時候，Merge Sort 可以透過快慢指針穩定將 Linked List 一分為二，保持時間複雜度為 O(nlogn)，而 Quick Sort 在選取 Pivot（錨點）上就較 Array 上的隨機存取差很多。

CHANGELOG

日期	敘述
2025-03-17	更新 Time / Space Complexity 及總結
2021-11-18	初版

#algorithm