合併排序：分一半、各自排、再合起來

想像你跟同學分工

桌上有 100 張牌要排。一個人排太累—— 找個同學分一半，你排 50 張、他排 50 張，最後把兩疊合在一起。

如果還是太多怎麼辦？繼續分！ 50 → 25 → 12 → 6 → 3 → 2 → 1

切到一張時就不用排了（一張一定是「排好的」）。然後從最小份開始兩兩合併。

這就是「分治法 (Divide and Conquer)」的精神。

看一個完整的例子

排 [5, 3, 8, 1, 4, 7, 2, 6]：

切階段（一直對半切到剩一個）：

[5, 3, 8, 1, 4, 7, 2, 6]
        |
   [5,3,8,1]      [4,7,2,6]
     |                |
  [5,3]  [8,1]    [4,7]  [2,6]
   |  |   |  |     |  |   |  |
  [5][3] [8][1]   [4][7] [2][6]

合階段（兩兩合併成排好的）：

  [5][3] → [3,5]   [8][1] → [1,8]   [4][7] → [4,7]   [2][6] → [2,6]
       \      /              \      /
       [1,3,5,8]              [2,4,6,7]
              \              /
              [1,2,3,4,5,6,7,8] ✓

合併兩個排好的陣列（核心動作）

這是 Merge Sort 最重要的子問題： 已知 L 和 R 都排好了，怎麼把它們合成一個排好的陣列？

想成兩疊牌都正面朝上： 比較兩疊的最上面那張，小的拿出來放到結果裡，重複直到拿完。

例：L = [1, 3, 5, 8]、R = [2, 4, 6, 7]

步驟	L 剩	R 剩	結果
比 1 vs 2，拿 1	[3,5,8]	[2,4,6,7]	[1]
比 3 vs 2，拿 2	[3,5,8]	[4,6,7]	[1,2]
比 3 vs 4，拿 3	[5,8]	[4,6,7]	[1,2,3]
比 5 vs 4，拿 4	[5,8]	[6,7]	[1,2,3,4]
比 5 vs 6，拿 5	[8]	[6,7]	[1,2,3,4,5]
比 8 vs 6，拿 6	[8]	[7]	[1,2,3,4,5,6]
比 8 vs 7，拿 7	[8]	[]	[1,2,3,4,5,6,7]
R 空了，倒出 L	[]	[]	[1,2,3,4,5,6,7,8]

💡關鍵直覺

合併 n 個元素 → 每張牌看一次 → O(n)。切割了 log n 次 → 總共 O(n log n)。

Pseudocode

Algorithm MergeSort(A, left, right):

if left ≥ right: return // 只剩一個，停

mid ← (left + right) / 2

MergeSort(A, left, mid) // 排左半

MergeSort(A, mid+1, right) // 排右半

Merge(A, left, mid, right) // 合起來

複雜度

情境	Big-O
最壞	O(n log n)
平均	O(n log n)
最好	O(n log n)
空間	O(n) — 需要額外陣列存合併結果

⚠️跟 O(n²) 比有多誇張

n = 1,000,000 時：

O(n²) 跑 1 兆次 → 慢到天荒地老
O(n log n) 跑 2 千萬次 → 不到 1 秒

這就是為什麼真實世界的排序庫都用 O(n log n) 等級的演算法。

📝考試會這樣考

題型一：畫遞迴樹。 給陣列，要你畫出 Merge Sort 的「切割樹」和「合併樹」。訣竅：對半切到剩一個，再倒著合回去。每一層寫清楚分到的子陣列。

題型二：算複雜度（這是經典）。

遞迴關係式： $T(n) = 2T(n/2) + O(n)$

用 Master Theorem 解出 T(n) = O(n log n)。

怎麼直觀理解：

切割了 log n 層
每層合併總共要花 O(n)
所以總共 層數 × 每層成本 = log n × n = O(n log n)

題型三：為什麼 Merge Sort 是 stable（穩定）？ 合併時如果 L 和 R 的最上面相等，先拿 L 的——這樣相同值的相對順序不變。

這章記住

分一半 → 各自排 → 合起來，這個套路叫分治 (Divide and Conquer)。
合併兩個排好陣列只需 O(n)，總共 O(n log n)。
缺點：需要額外的空間 O(n)。