「最優排序演算法」是否存在？答案取決於你如何定義「優」。若以比較次數最少為唯一指標，在比較模型下存在理論下界；但工程上還須考慮移動次數、快取友好度、平行化、空間開銷等。本文聚焦比較決策樹模型，推導最壞情況下的比較下界，並詳細解析 Ford-Johnson Merge-Insertion Sort 如何逼近該下界。
任何比較排序過程皆可對應一棵二元決策樹：
K_i : K_j，左分支 K_i < K_j，右分支 K_i > K_j。a_1, a_2, ..., a_n 表示 K_{a_1} < K_{a_2} < ... < K_{a_n}。對 n 個元素，葉節點數 = n!。高度為 h 的二元樹最多 2^h 葉，故 n! ≤ 2^h ⇒ h ≥ ⌈log₂(n!)⌉。此即最壞情況最少比較次數 S(n) 的下界。
Binary Insertion、Tree Selection、Two-way Merging 的最壞比較次數為：
C(n) = ∑_{k=1}^{n} ⌈log₂ k⌉
對小 n 計算：
| n | ⌈log₂(n!)⌉ | C(n) | 差距 |
|---|---|---|---|
| 4 | 5 | 5 | 0 |
| 5 | 7 | 8 | 1 |
| 21 | 66 | 67 | 1 |
Binary Insertion 在 n=5 時比下界多 1 次。如何達成 S(5)=7？
K₁:K₂、K₃:K₄（2 次），較大者再比較（第 3 次），得 a < b < d，c < d。e 用二分插入 a,b,d：先比 b，再比 a 或 d（最多 2 次）。c 插入 a,b,d,e：比 e，再比 a 或 b（最多 2 次，c:d 已知）。n 個元素兩兩比較，取較大者組成 ⌊n/2⌋ 個「大元素」，小元素保留（⌊n/2⌋ 次）。⌊n/2⌋ 個大元素遞迴用 Merge-Insertion 排序，形成主鏈 a₁ < a₂ < ... < a_m（m = ⌊n/2⌋），對應小元素為 b₁, b₂, ..., b_m（a_i 勝過 b_i）。b_i 依特定順序二分插入主鏈。關鍵在於插入順序與分組大小的設計，使每組插入的比較次數恰好等於 ⌈log₂(當前主鏈長度+1)⌉，避免主鏈長度剛好超過 2 的冪導致額外比較。定義序列 T_k 滿足遞迴：
T₀ = 1, T₁ = 1
T_k + T_{k-1} = 2^k
得 T = 1, 3, 5, 11, 21, 43, 85, ...（Jacobsthal 數列變體）。
第 k 組插入 T_k - T_{k-1} 個元素，每個需 k 次比較。此安排確保主鏈長度在插入該組前為 2^k - 1，二分查找恰需 k 次，零浪費。
S(10)=22）。b₁, a₁, a₂, ..., a₁₀）。b₃, b₂（2 元素，各 2 次）b₅, b₄（2 元素，各 3 次）b₁₁, b₁₀, b₉, b₈, b₇, b₆（6 元素，各 4 次）⌈log₂(21!)⌉。為何先插 b₁₁？因插入後主鏈長 16，二分需 5 次；但 b₁₁ 已知 > a₁₀，實際搜尋空間 15，僅需 4 次。若先插 b₆，後插 b₁₁ 時主鏈已達 16，需 5 次，總和超標。
Merge-Insertion 是比較排序最壞情況比較次數最優的演算法（對所有 n 均達到 ⌈log₂(n!)⌉ 或極接近）。然而它不具備實用優勢：資料移動多、快取表現差、實作複雜、難以平行化。其價值在於：
工程上，std::sort (IntroSort) 以 O(n log n) 平均、O(n log n) 最壞（堆排序兜底）、優秀快取局部性、簡單實作，綜合效能遠超 Merge-Insertion。理解理論極限，是為了在權衡中做出更明智的選擇。
