合併排序在做什麼
合併排序是「分而治之」：把大問題切成小問題，解決後再合起來。
- 拆分：把區間從中間切成左右兩半，各自遞迴處理，直到只剩一個數字。只有一個數字的區間一定是已排序的。
- 合併：兩個已排序的半邊要合成一個。每次比較兩邊最前面的數字，把較小的先放進結果，重複到其中一邊用完，再把另一邊剩下的接在後面。
- 回到上一層，繼續合併，直到整個陣列合併完成。
怎麼讀這張圖
- 上方的遞迴樹：每一層是一列，欄位對齊原陣列的索引。虛線框是已經切開的區間，淡藍底是已經排好的區間，粗框是目前正在處理的那一段。
- 下方的合併區：左半、右半與合併結果三列。已被取走的數字會劃線，剛取走的那個是實心；兩邊目前最前面的數字以粗框標出，也就是這一步正在比較的對象。
- 右側的呼叫堆疊：還沒有返回的遞迴呼叫，最上面是目前這一層。堆疊最深只有 ⌈log₂ n⌉ + 1，不會隨著資料量快速變大。
為什麼是 O(n log n)
7 個數字切成一半一半，只要 3 層就會切到單一數字，所以層數是 log n。每一層的合併，所有數字各被比較並寫入至多一次，合起來是 n。層數乘上每層的工作量，就是 n log n。
試著按「已排序」或「隨機」比較看看：比較次數會有些差異，但寫入次數幾乎一樣，因為每個數字在每一層都要被寫入一次。
複雜度
| 最佳 | O(n log n) |
|---|---|
| 平均 | O(n log n) |
| 最差 | O(n log n) |
| 額外空間 | O(n) |
| 穩定 | 是 |
常見問題
- 合併排序為什麼不管資料長怎樣都是 O(n log n)？
- 因為它每次都固定從中間切成兩半，一共切 log n 層；而每一層合併時，所有數字各被處理一次，合起來是 n。資料已排好或完全反序，步驟數幾乎一樣。
- 合併排序需要多少額外空間？
- 合併時要暫存左右兩半，所以是 O(n)。這是它和快速排序最大的取捨：換來穩定與固定的 O(n log n)，付出額外記憶體。
- 合併排序是穩定的嗎？
- 是。兩邊比到相等的數字時一律先取左邊，相等元素的相對順序不會改變。
- 什麼時候適合用合併排序？
- 需要穩定排序、要保證最差情況也是 O(n log n)，或資料放在不適合隨機存取的地方（例如鏈結串列、磁碟上的大檔案）時。