排序算法之：基于“最小比较数排序”（Ford-Johnson Merge-Insertion Sort）的递推关系与比较次数下界分析
题目描述
Ford-Johnson 算法（通常称为 Merge-Insertion Sort）是一种基于比较的排序算法，其目标是在最坏情况下最小化比较次数。该算法通过巧妙地结合归并（Merge）和插入（Insertion）策略，在最坏情况下实现了接近信息论下界（约为 n log₂ n - 1.415n）的比较次数。本题要求：深入分析 Ford-Johnson 算法的递推关系，并严格证明其比较次数下界，阐述其最优性在比较排序中的意义。
解题过程
步骤1：回顾 Ford-Johnson 算法的基本框架
Ford-Johnson 算法对 n 个元素排序分为两大阶段：
- 成对比较与分组：将元素两两比较，形成 ⌈n/2⌉ 个有序对（每个对中较小者称为“较小元”，较大者称为“较大元”）。然后递归地对所有“较小元”排序（递归调用自身）。
- 插入阶段：将排序后的“较小元”序列作为主链，然后按照一种精心设计的顺序，将剩余的“较大元”通过二分插入逐个插入主链，以最小化比较次数。
步骤2：递推关系的形式化
设 C(n) 表示 Ford-Johnson 算法对 n 个元素排序所需的最坏情况比较次数。算法步骤可拆解：
- 步骤1（成对比较）：进行 ⌈n/2⌉ 次比较，得到 ⌈n/2⌉ 个有序对。
- 步骤2（递归排序较小元）：对 ⌈n/2⌉ 个较小元递归排序，比较次数为 C(⌈n/2⌉)。
- 步骤3（插入较大元）：将剩余的 ⌊n/2⌋ 个较大元按特定顺序插入已排序的较小元链。插入顺序由 Jacobsthal 数决定，保证每次插入时二分查找的成本最优。
插入顺序的数学原理
在已排序的较小元链中插入第 j 个较大元时，其二分查找的比较次数 ≈ ⌈log₂ (j+1)⌉。但 Ford-Johnson 算法通过一种“最优顺序”安排插入，使得总比较次数最小。这个顺序由 Jacobsthal 数 生成：序列 Jₖ 满足 J₀=0, J₁=1, Jₖ = Jₖ₋₁ + 2Jₖ₋₂。算法先插入索引为 J₂, J₃, ... 对应的较大元，这样可以利用之前插入元素建立的“比较信息”减少后续查找成本。
递推公式推导
通过分析插入过程，得到递推关系（n ≥ 2）：
\[C(n) = \lceil n/2 \rceil + C(\lceil n/2 \rceil) + \sum_{i=1}^{\lfloor n/2 \rfloor} \lceil \log_2(3i/2) \rceil \]
其中最后一项是插入所有较大元的总比较次数下界（经过 Jacobsthal 顺序优化后的近似）。
步骤3：递推关系的求解与下界分析
通过数学归纳法或生成函数法，可证明：
\[C(n) = n \log_2 n - 1.415n + O(\log n) \]
更精确的表达式为：
\[C(n) = n \log_2 n - n \cdot (1 + \frac{1}{2} + \frac{1}{4} + \cdots + \frac{1}{2^{\lfloor \log_2 n \rfloor}}) + O(\log n) \]
当 n 是 2 的幂时，可简化为：
\[C(n) = n \log_2 n - (2 - \lg 3) n + O(\log n) \approx n \log_2 n - 1.415 n + O(\log n) \]
步骤4：与信息论下界的比较
比较排序的信息论下界为 ⌈log₂(n!)⌉。利用斯特林公式：
\[\log_2(n!) = n \log_2 n - n \log_2 e + O(\log n) \approx n \log_2 n - 1.443 n + O(\log n) \]
因此 Ford-Johnson 算法的比较次数 n log₂ n - 1.415n 与下界 n log₂ n - 1.443n 仅相差约 0.028n，是所有已知基于比较的排序算法中最接近下界的。
步骤5：最优性证明
Ford-Johnson 算法在 n ≤ 15 时被证明是最坏情况最优的（通过穷举所有决策树）。对于更大的 n，目前没有算法被证明在最坏情况下比它更优。其递推关系实际上是通过“决策树最小化”构造的：在每一步，算法选择比较，使得两个子树的大小尽可能平衡，同时利用历史信息减少后续比较。
步骤6：实际意义与局限性
- 意义：Ford-Johnson 算法是理论上的里程碑，展示了如何通过精心设计插入顺序来逼近比较次数下界。
- 局限性：由于需要复杂的顺序控制和二分查找，其常数因子较大，实际运行时间可能不如快速排序等高效算法，因此主要用于理论研究。
总结
Ford-Johnson 算法通过递推关系 C(n) = ⌈n/2⌉ + C(⌈n/2⌉) + 优化插入代价，实现了接近信息论下界的比较次数。其递推关系的解 n log₂ n - 1.415n 是当前基于比较排序的最优上界之一，体现了在比较模型下算法设计的精细优化。