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 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 | 初版 |