巧思藏在哪裡
上一篇導覽給了我們「分／治／合」的範本，並提醒：這三步裡通常有一步扛起整個演算法。合併排序 正是這個提醒最乾淨的例證。它的分割步驟近乎平凡到失禮——直接按索引把 n 個元素的陣列切成兩半，完全不動腦——而它的治步驟不過是對兩半各做一次遞迴呼叫。所有的設計功夫、所有的執行時間，都住在 合併步驟 裡：把兩個各自已排序的半邊，編織成一個整體有序的結果。
把它和下一篇要談的快速排序對照，會看到相反的取捨。快速排序在分割上下足功夫（繞著樞紐做分割），好讓它的合併步驟免費——各部分就地排好後，再沒事可做。合併排序押的是對稱的賭注：平凡的分割、昂貴的合併。把兩者並排來看才是真正的功課，因為它顯示「分治」不是某一個演算法，而是一筆你可以選擇花在哪一步的預算。合併，正是合併排序決定花錢的地方。
親手追蹤一次合併
想像桌上兩疊各自有序、牌面朝上的牌，每疊最小的在最上面。要合併它們，你只比較兩疊最上面的兩張牌，把較小的那張移到輸出疊，然後重複。因為每疊本就有序，你尚未放下的最小牌永遠是這兩個頂端之一——絕不會是埋在底下的——所以只比較最前面一張就足以正確選擇。當一疊空了，另一疊本就有序，你便把它剩下的整批直接掃進輸出、原封不動。這就是 合併排序 的合併全部的想法。
- 放下兩根讀取手指：i 指向左半 L 的最前端、j 指向右半 R 的最前端，並備一個空的輸出串列。
- 當兩半都還有牌時：比較 L[i] 與 R[j]，把較小者複製到輸出，並只推進那一半的手指。相等時兩邊皆可（先取左邊以維持穩定性）。
- 當其中一半用完時，把另一半剩下的牌整批照抄到輸出——它們本就有序。
- 此時輸出已含全部 n 個元素並排好序；每個元素恰被複製一次。
為什麼結果是正確的，而不只是看起來合理？握住一條迴圈不變量：在每一步開始時，輸出串列依序恰好含有比當前兩個前端 L[i] 與 R[j] 都小的那些元素。起初它成立（輸出為空）。每一步都維持它：我們附加兩個前端中較小者，而那正是任何地方尚未放入的最小元素，因此它正確地延長了已排序的前綴。當迴圈結束時兩半皆已耗盡，故由不變量可知輸出就是完整的有序合併結果。正確性來自這個論證，而非來自圖看起來整齊。
為合併計數
把兩個合計 n 個元素的半邊合併一次有多貴？每次比較恰好把一個元素送進輸出，而我們從不重看任一元素，所以比較次數至多 n - 1，而總工作量——比較加複製——是 Theta(n)。這就是關鍵事實：合併與合計規模成線性。它也解釋了一個人們常忘記的隱藏成本。合併不易就地完成；它寫入一個獨立的輸出緩衝區，所以合併排序需要 O(n) 的額外暫存記憶體。這份速度有一部分是用空間買來的。
現在把整個演算法疊成一條遞迴關係式。對 n 個元素排序，要付出兩次規模 n/2 的遞迴排序，加上一次線性合併：這就是標準的 分治遞迴關係式 T(n) = 2 T(n/2) + O(n)，基底情況為 T(1) = O(1)。幾乎每一個快速的分治排序或搜尋都會產生這條方程式的親戚，所以學會讀它，比背下合併排序的答案更有價值。
T(n) = 2 T(n/2) + c*n # 2 subproblems of half size, linear merge
level subproblems merge work each row total
0 1 c*n c*n
1 2 c*n/2 c*n
2 4 c*n/4 c*n
... ... ... ...
log n n c c*n
---------------
rows = log n + 1, each c*n -> total = c*n*(log n + 1) = O(n log n)遞迴樹法 讓答案幾乎看得見。深度 0 有一個規模 n 的問題；深度 1 有兩個規模 n/2 的；深度 k 有 2^k 個規模 n/2^k 的。任一層的合併工作量是（片數）乘（每片規模）= 2^k 乘 n/2^k = n，所以每一層都花同樣的 Theta(n)。減半在約 log2(n) 層後停止，此時每片規模降為 1。把每層工作量乘上層數：Theta(n) 乘 Theta(log n) = Theta(n log n)。主定理 立刻確認此事——當 a=2、b=2 時，每層成本恰與 n 相符，正是它的平手情況——但遞迴樹告訴你「為什麼」，而不只是「是這樣」。
每一次都是同樣的 n log n
一個低調而非凡的性質：合併排序對每一種輸入都跑在 Theta(n log n)——無論已排序、逆序，還是打亂。切割按索引進行，所以遞迴樹的形狀從不依賴資料，而合併總是做它的線性掃描。因此合併排序的最壞情況、最好情況與平均情況三者一致。這相對於快速排序是個真正的優勢：快速排序的期望時間是 O(n log n)，但對某個不走運的輸入，其最壞情況是 O(n^2)。合併排序則沒有不走運的輸入——可預測性正是你買到的東西之一。
合併還有一份迷人的兼差。如果每次你從右半複製一個元素、而左半還有元素在等待時，你就加上那些等待中左半元素的個數，這個累計總和正是原陣列中 逆序對——順序顛倒的配對——的數目。因此合併排序順手就在 O(n log n) 內數出逆序對，遠勝於檢查所有配對那種顯而易見的 O(n^2) 做法。這是個小而誠實的示範：合併步驟不只是記帳；你在合併時所做的工作，可以算出某種真正全新的東西。
以比較為基礎的排序能更快嗎？
人會自然地盼望有某種更聰明、以比較為基礎的排序能打敗 n log n。出人意料地，沒有任何一個能做到——而原因是一個乾淨的計數論證，不是想像力的不足。任何只靠比較配對來排序的方法，都能畫成一棵 決策樹：每個內部節點問「a < b 嗎？」並分出兩條岔路，而每片葉子是演算法可能輸出的一種最終排序。要正確排序 n 個相異元素，這棵樹對每一種可能的答案都必須有至少一片可達的葉子，而可能的排序共有 n! 種。
一棵高度為 h 的二元樹至多有 2^h 片葉子，所以我們需要 2^h >= n!，由此得 h >= log2(n!)。依標準估計 log2(n!) 是 Theta(n log n)，故這棵樹的高度——最壞情況的比較次數——是 Omega(n log n)。高度是最長的根到葉路徑長度，也就是某個輸入所逼出的最多比較次數，所以這對「以比較為基礎的排序」這整個類別的最壞情況比較次數，是一個真正的下界。合併排序達到了它。這使得它的 O(n log n) 不只是好，而是在以比較為基礎的方法之中 漸進最佳。