合併排序

🎯 什麼情境該想到我

當你「需要「穩定」與「最差情況也保證 $O (n lo g n)$ 」這兩個保證」的時候。
★ 它比快速排序慢，卻是外部排序、平行排序、穩定排序這三個場景的唯一選擇。

⚙️ 怎麼用（機制與推導）

運作機制：分治三步

Divide  : 切成兩半（O(1)，只是算中點）
Conquer : 遞迴排序兩半
Combine : ★ 合併兩個已排序的序列（O(n)，整個演算法的重點在這）

合併是核心：兩個已排序序列，各放一根指標，每次取較小的那個。

左: [2 4 5]   右: [1 3 6]
     ↑              ↑        取 1
     ↑                ↑      取 2
       ↑              ↑      取 3
       ↑                ↑    取 4 → 5 → 6
結果: [1 2 3 4 5 6]

func MergeSort[T cmp.Ordered](a []T) {
    buf := make([]T, len(a))   // ★ 只配置一次，不要在遞迴裡每次 make
    mergeSort(a, buf)
}
 
func mergeSort[T cmp.Ordered](a, buf []T) {
    if len(a) < 2 {
        return
    }
    mid := len(a) / 2
    mergeSort(a[:mid], buf[:mid])
    mergeSort(a[mid:], buf[mid:])
    merge(a, mid, buf)
}
 
func merge[T cmp.Ordered](a []T, mid int, buf []T) {
    i, j, k := 0, mid, 0
    for i < mid && j < len(a) {
        // ★ 這裡必須是 <=，否則相等時會取右邊，穩定性就沒了
        if a[i] <= a[j] {
            buf[k] = a[i]; i++
        } else {
            buf[k] = a[j]; j++
        }
        k++
    }
    k += copy(buf[k:], a[i:mid])
    copy(buf[k:], a[j:])
    copy(a, buf)
}

★ 複雜度推導（主定理 Case 2）

$T (n) = 兩個子問題 2 \cdot T (\frac{n}{2}) + 合併 Θ (n)$

對照主定理 $T (n) = a T (n / b) + f (n)$ ： $a = 2$ 、 $b = 2$ → $n^{l o g_{b} a} = n^{l o g_{2} 2} = n$ 。
$f (n) = Θ (n) = Θ (n^{l o g_{b} a})$ → Case 2 → $T (n) = Θ (n lo g n)$ 。

不用主定理的直覺版：遞迴樹有 $lo g_{2} n$ 層，每一層的合併總成本都是 $Θ (n)$ （每層處理的元素總數不變）→ $Θ (n lo g n)$ 。

層 0:  ────────── n ──────────         合併成本 n
層 1:  ──── n/2 ────  ──── n/2 ────    合併成本 n
層 2:  ─ n/4 ─ ─ n/4 ─ ─ n/4 ─ ─ n/4 ─ 合併成本 n
       ⋮                                   ⋮       共 log n 層

這是最差、平均、最佳都一樣的 $Θ (n lo g n)$ ——沒有壞情況。

四個性質

性質	說明
穩定	✅（靠 `<=`）
原地	❌ 需要 $Θ (n)$ 輔助空間 —— 這是它最大的代價
最差保證	✅ $Θ (n lo g n)$ ，不像快排會退化
★ 只需要順序存取	合併時兩邊都是從頭讀到尾

★ 那個「只需順序存取」是它真正的殺手鐧

三個場景因此只能用它：

場景	為什麼
外部排序（資料大於記憶體）	合併只需要順序讀取檔案／磁碟／網路串流。經典做法：切成能塞進記憶體的段各自排好寫回磁碟（run），再做多路合併。 ★ 快速排序需要隨機存取，在磁碟上是災難
鏈結串列排序	合併不需要隨機存取 → 鏈結串列上可以做到 $O (1)$ 額外空間（只改指標，不搬資料）。這是唯一一個在鏈結串列上漂亮的 $O (n lo g n)$ 排序（見鏈結串列）
平行排序	左右兩半完全獨立，可以並行遞迴。合併階段也可平行化

★ TimSort：實務上你真正在用的東西

TimSort = 合併排序 + 插入排序 + 「偵測既有的有序片段」

掃描找出天然遞增/遞減的 run（真實資料常常有大段已排序）
太短的 run 用二分插入排序補到最小長度（見插入排序）
依一套平衡規則合併這些 run

語言/執行環境	排序實作	穩定？
JS（V8）`Array.prototype.sort`	TimSort（V8 7.0 起）	✅ 保證穩定（ES2019 起是規格要求）
Python `sorted` / `list.sort`	TimSort	✅
Java `Arrays.sort(Object[])`	TimSort	✅
Go `slices.Sort`	pdqsort（快排家族）	❌ 不穩定。要穩定用 `slices.SortStableFunc`

★ 「為什麼 JS 的 sort 是穩定的、Go 的不是」——答案就是這張表。
Node.js 那側你可以依賴穩定性；Go 那側不可以，除非明確用 SortStableFunc。

🧪 我實際套用的紀錄

（待填）

⚠️ 注意 / 什麼時候不適用

★ 記憶體是主要限制。 $Θ (n)$ 輔助空間，排 1 GB 資料就要多 1 GB。記憶體吃緊時用堆積排序（原地且有保證）。
不要在遞迴裡 make 緩衝區。每層都配置會產生大量 GC 壓力——配置一次傳下去（見上面程式碼）。
實務上比快速排序慢。雖然同為 $Θ (n lo g n)$ ，但快排原地、快取友善、常數小（見快速排序）。
原地合併排序存在但不值得。有 $O (1)$ 空間的合併演算法，但常數極大，實務上沒人用。
小陣列上要切換成插入排序，否則遞迴開銷會吃掉優勢。
不要自己寫。Go 用 slices.SortStableFunc，JS 直接用 Array.prototype.sort。

🔗 相關工具

分治法 —— 這是分治的教科書範例，主定理 Case 2
插入排序 —— TimSort 的另一半
快速排序 —— 對照組：快但不穩定、最差 $O (n^{2})$
堆積排序 —— 對照組：原地且有保證，但快取不友善
鏈結串列 —— 合併排序在鏈結串列上特別漂亮
演算法導論

Quartz 5

Explorer