Learning Objectives
- 用兩個指標把兩個已排序的串列合併成一個，說明最多比較幾次
- 追蹤合併排序的遞迴：切成兩半、各自排好、再合併
- 說明合併排序為什麼是 O(n log n)：每一層合計搬 n 個元素，一共約 log₂n 層
- 說明合併排序需要 O(n) 的額外空間，而且是穩定排序
- 說出分治法的三個步驟，並用它寫出 O(log n) 的快速冪
兩疊已經排好的考卷
上一課的三種排序最壞都是 O(n²)：一百萬筆資料要比較約五千億次。這一課換一個想法。
假設兩位助教各自把一半的考卷依分數排好了，你要把兩疊合成一疊。你不需要重新排序，只要每次看兩疊最上面那一張，拿比較小的放到新的一疊，直到兩疊都拿完。 每拿一張只比一次，n 張考卷最多比 n - 1 次就合完了。
這就是合併（merge）。把它和遞迴結合起來：
- 陣列太大？切成兩半
- 兩半各自用同樣的方法排好（遞迴）
- 把兩個排好的半邊合併
這就是合併排序（merge sort），通常歸功於 John von Neumann 在 1945 年寫下的程式。它最壞情況也只要 O(n log n)。
合併兩個已排序的串列：兩個指標往前走
每一輪只比較 a[i] 和 b[j] 兩個元素，把小的放進 res，那一邊的指標往前一格。a 先用完之後，b 剩下的 52 已經排好，而且一定比 res 裡的都大，直接接在後面，不用再比。9 個元素只比較了 8 次。
合併要比較幾次
兩邊合計 n 個元素時：
- 每比較一次，就有一個元素放進結果，所以比較次數最多 n - 1 次（最後一個元素不用比）
- 如果一邊很早就用完（例如左邊全部都比右邊小），比較次數會更少，最少是比較短的那一邊的長度
- 每個元素都要放進結果一次，所以合併的工作量是 O(n)
相等時先拿左邊（a[i] <= b[j] 用 <=，不是 <）：這樣原本在前面的元素合併後仍在前面，合併排序就是穩定的（穩定排序見第 06 課）。
合併排序：切兩半、各自排好、再合併
合併排序的函式 merge_sort(a, lo, hi) 負責排好 a[lo..hi)（含 lo、不含 hi，和第 04 課的半開區間相同）：
def merge_sort(a, lo, hi):
if hi - lo <= 1: # 終止條件：0 或 1 個元素，本來就排好了
return
mid = (lo + hi) // 2
merge_sort(a, lo, mid) # 排好左半邊
merge_sort(a, mid, hi) # 排好右半邊
merge(a, lo, mid, hi) # 合併
merge 和上一個範例的做法相同，只是兩個半邊都在同一個陣列裡：左半邊是 a[lo..mid)、右半邊是 a[mid..hi)。
範例把三個 while 迴圈寫成一個：「右邊已經用完，或左邊還有而且比較小」就拿左邊，否則拿右邊。結果先放進暫存陣列 tmp，最後再抄回 a。
合併排序：遞迴樹與每一次合併
遞迴樹先一路往左切到只剩一個元素，回來時才開始合併：[38] 和 [27] 合成 [27, 38]，[43] 和 [3] 合成 [3, 43]，再把這兩段合成 [3, 27, 38, 43]……每一次合併都從兩個已經排好的半邊開始。8 個元素切了 3 層，樹的高度就是 log₂8 = 3。
為什麼是 O(n log n)
把遞迴樹一層一層看：
| 層 | 這一層有幾段 | 每段長度 | 這一層合併時一共搬幾個元素 |
|---|---|---|---|
| 0 | 1 | n | n |
| 1 | 2 | n/2 | n |
| 2 | 4 | n/4 | n |
| … | … | … | n |
| 最底層 | n | 1 | 不用合併 |
每往下一層，段數變成 2 倍、長度變成一半，所以每一層合計都是 n 個元素。長度從 n 一路對半到 1，要切 log₂n 次，一共 log₂n 層要合併。 總工作量就是 n × log₂n，也就是 O(n log n)。而且不管資料原本長什麼樣子，切法都一樣，所以最好、最壞、平均都是 O(n log n)。
下面的範例不排序，只依合併排序的切法走一遍，把每一層合併時要搬的元素個數加起來。
數一數每一層的工作量
16 個元素切成 4 層要合併（長度 16、8、4、2），第 5 層的 16 個單獨元素不用合併。看 work 的四格：最後每一格都是 16，總共 16 × 4 = 64。如果 n 是 1,000,000，大約是 20 層 × 一百萬 = 兩千萬，和 O(n²) 的五千億次差了兩萬多倍。
合併排序的代價：額外的空間
合併時要把結果先放進暫存陣列 tmp，再抄回原陣列，所以合併排序需要 O(n) 的額外空間（另外遞迴本身要 O(log n) 層的堆疊）。
這和第 06 課三種原地排序只用 O(1) 額外空間不同。資料很大、記憶體很緊的時候，這是要考慮的代價。
| 選擇／插入／氣泡 | 合併排序 | |
|---|---|---|
| 最壞時間 | O(n²) | O(n log n) |
| 最好時間 | O(n²)／O(n)／O(n) | O(n log n) |
| 額外空間 | O(1) | O(n) |
| 穩定 | 選擇不穩定，插入與氣泡穩定 | 穩定 |
合併排序的穩定性和「不怕資料長怎樣」，讓它被許多語言的內建排序採用或改良：Python 的 sorted()、Java 對物件陣列的 Arrays.sort 都使用以合併排序為基礎的 Timsort。
下面的排序賽跑加入了合併排序。資料量越大，O(n log n) 和 O(n²) 的差距越明顯；但在已經排好的資料上，插入排序反而比較快。
想一想：合併與合併排序
用本課的方法合併 [1, 3, 5] 和 [2, 4, 6]，下面的程式會印出什麼？
a, b = [1, 3, 5], [2, 4, 6]
i = j = comparisons = 0
while i < len(a) and j < len(b):
comparisons += 1
if a[i] <= b[j]:
i += 1
else:
j += 1
print(comparisons)
用合併排序排 1,024 個元素，遞迴樹有幾層要合併？總共大約搬幾次元素？
把 merge 裡的 a[i] <= a[j] 改成 a[i] < a[j]，排序結果會怎樣？
分治法：同一招解別的問題
合併排序是分治法（divide and conquer）的代表。分治法的三個步驟：
- 分（divide）：把問題切成幾個規模較小、形式相同的子問題
- 治（conquer）：用遞迴解決子問題；子問題夠小時直接回答
- 合（combine）：把子問題的答案組合成原問題的答案
第 05 課的遞迴版二分搜尋也是分治法的一種：切一半之後只需要處理其中一半，而且不用「合」。
快速冪：要算 xⁿ，直接連乘要做 n - 1 次乘法。分治的想法是：
- n 是偶數：xⁿ = (x^(n/2))²
- n 是奇數：xⁿ = (x^(n/2))² × x（這裡 n/2 是整數除法）
- 終止條件：x⁰ = 1
x^(n/2) 只算一次，存在變數 half 裡再自己乘自己。每一層 n 變成一半，所以只要約 log₂n 層，每層一到兩次乘法，是 O(log n)。
範例用 long long／long 存結果，避免 C++、Java 的 int 溢位（3¹³ 和 2³⁰ 其實還在 int 範圍內，但次方稍大就會超過）。
快速冪：3 的 13 次方只要 5 次呼叫
遞迴樹是一條直線：13 → 6 → 3 → 1 → 0，每一層 n 減半。回來的路上，每一層把 half 自己乘自己，n 是奇數時再多乘一個 3。2³⁰ 也只要 6 次呼叫（30 → 15 → 7 → 3 → 1 → 0），連乘則要 29 次乘法。
想一想：快速冪的呼叫次數
下面的程式數一數 power(2, 16) 呼叫了幾次 power，會印出什麼？
calls = 0
def power(x, n):
global calls
calls += 1
if n == 0:
return 1
half = power(x, n // 2)
if n % 2 == 0:
return half * half
return half * half * x
power(2, 16)
print(calls)
如果把 half * half 寫成 power(x, n // 2) * power(x, n // 2)（不用變數存起來），算 2¹⁶ 會怎樣？
實作：用分治法找最大值
請用分治法完成 max_of(a, lo, hi)（C++／Java 叫 maxOf）：回傳閉區間 a[lo..hi] 裡的最大值。只有一個元素時直接回傳；否則從中間切開，分別找出左右兩半的最大值，回傳比較大的那一個。
重點整理
- 合併兩個已排序的串列：兩個指標各指一邊，每次取比較小的；n 個元素最多比較 n - 1 次，O(n)
- 合併排序：切成兩半、各自遞迴排好、再合併；終止條件是只剩 0 或 1 個元素
- 每一層合計搬 n 個元素，一共 log₂n 層，所以最好、最壞、平均都是 O(n log n)
- 合併需要暫存陣列，額外空間 O(n)；相等時先拿左邊，所以是穩定排序
- 分治法三步驟：分、治、合。快速冪把 xⁿ 變成 (x^(n/2))²，子問題只算一次，O(log n)
下一課：快速排序。它也是分治法，但把功夫花在「切」的時候：選一個基準，把小的放左邊、大的放右邊，合併這一步就省掉了。