排序算法之：基于“最小比较数排序”（Ford-Johnson Merge-Insertion Sort）的递推关系与比较次数下界分析
题目描述
Ford-Johnson 算法，又称 Merge-Insertion Sort，是一种旨在最小化比较次数的排序算法。它通过精心设计的合并与插入策略，在比较模型下实现了接近信息论下界的比较次数。本题要求深入分析该算法的递推关系，并证明其最坏情况比较次数下界。已知对 n 个元素排序，该算法的最坏比较次数满足递推关系：
C(n) = C(⌊n/2⌋) + C(⌈n/2⌉) + M(⌊n/2⌋, ⌈n/2⌉) + I(n)，
其中 M(a, b) 是合并两个已排序序列所需的最坏比较次数，I(n) 是插入剩余元素所需的比较次数。请逐步推导该递推关系，并分析 C(n) 的渐进下界。
解题过程
1. 算法核心思想回顾
Ford-Johnson 算法分为两大阶段：
- 分组与内部排序：将 n 个元素两两比较，形成 ⌊n/2⌋ 个“胜者”（较大者）和 ⌊n/2⌋ 个“败者”。对胜者组递归排序，从而确定一个主链（main chain）。
- 败者插入：将败者依次插入主链，利用二分查找优化比较次数。
算法的关键在于败者插入顺序经过精心设计，使得每次插入时主链长度尽可能小，从而减少比较。
2. 递推关系推导
设 C(n) 为对 n 个元素排序的最坏比较次数。
步骤 2.1：分组与内部排序
- 将元素两两比较，花费 ⌊n/2⌋ 次比较，得到胜者组（大小 ⌈n/2⌉）和败者组（大小 ⌊n/2⌋）。
- 对胜者组递归排序，花费 C(⌈n/2⌉) 次比较。
- 此时胜者组已有序，形成初始主链。
步骤 2.2：合并胜者组与败者组
注意：败者组并未排序，但每个败者都小于其配对胜者。
- 将败者组视为另一个序列，但其元素无序，不能直接归并。
- 实际上，算法将败者插入主链的过程可视为一种“合并”，但比较次数不同于标准归并。
- 设 M(⌊n/2⌋, ⌈n/2⌉) 表示将败者组插入主链的最坏比较次数。
步骤 2.3：败者插入的优化顺序
- 败者插入顺序不是随机的，而是按特定顺序（Jacobsthal 数相关）分批插入，使得每次插入时主链长度接近二分查找最优情况。
- 设 I(n) 表示所有败者插入所需的总比较次数，包括二分查找开销。
步骤 2.4：递推关系建立
综合以上步骤：
- 两两比较：⌊n/2⌋ 次。
- 递归排序胜者组：C(⌈n/2⌉) 次。
- 败者插入：M(⌊n/2⌋, ⌈n/2⌉) 次。
但注意：步骤 1 的比较已包含在步骤 3 的插入中？需仔细区分。
实际更精确的递推：
- 先两两比较（⌊n/2⌋ 次），得到胜者组 S 和败者组 L。
- 递归排序 S（大小 m = ⌈n/2⌉），花费 C(m)。
- 将 L 插入已排序的 S 中，此时插入的比较次数记为 I(n)。
但在插入过程中，由于 L 中每个元素只与 S 中部分元素比较（二分查找），且 S 长度动态增长，故 I(n) 不是简单的 m×log m。
经典推导中，递推关系为：
C(n) = ⌊n/2⌋ + C(⌈n/2⌉) + I(n)，
其中 I(n) 是败者插入的比较次数，满足自己的子递推。
但为统一形式，可定义 M(a, b) 为合并两个序列的比较次数，这里一个序列有序（胜者组），另一个无序但元素有界（败者组）。然而，由于败者组元素间无大小关系，M(a, b) 实际就是 I(n)。
最终标准递推（见文献）：
C(n) = C(⌊n/2⌋) + C(⌈n/2⌉) + M(⌊n/2⌋, ⌈n/2⌉) + I(n) 是过度分解。
更准确是：
C(n) = ⌊n/2⌋ + C(⌈n/2⌉) + K(n)，
其中 K(n) 是败者插入的总比较次数，由 Jacobsthal 顺序决定。
3. 插入比较次数 I(n) 的细化分析
设 n 个元素，胜者组大小 m = ⌈n/2⌉，败者组大小 k = ⌊n/2⌋。
败者按特定顺序插入：
- 第一批插入的败者数量为某个 t₁，插入时主链长度为 m，每个败者用二分查找需 ⌈log₂(m+1)⌉ 次比较。
- 第二批插入时，主链长度变为 m + t₁，比较次数稍增。
Jacobsthal 顺序：
插入顺序由 Jacobsthal 数 Jᵢ 定义，确保总比较次数接近下界。
设第 i 批插入的败者数量为 dᵢ，插入时主链长度为 m + Σ_{j<i} dⱼ，比较次数为 dᵢ × ⌈log₂(当前主链长度 + 1)⌉。
近似公式：
I(n) ≈ Σ_{i=1}^{r} dᵢ × ⌈log₂(m + Σ_{j<i} dⱼ + 1)⌉，
其中 r 是批次数，dᵢ 由 Jacobsthal 序列决定。
4. 递推关系的渐进下界推导
步骤 4.1：简化模型
为求下界，忽略常数和取整，考虑近似递推：
C(n) ≈ n/2 + C(n/2) + I(n)。
其中 I(n) 可证明满足 I(n) ≥ (n/2) log₂(n/2) - O(n)。
步骤 4.2：代入求解
假设 C(n) 形式为 C(n) = n log₂ n - αn + o(n)，α 为某常数。
代入递推：
n log₂ n - αn ≈ n/2 + (n/2) log₂(n/2) - α(n/2) + (n/2) log₂(n/2) - O(n)。
化简右式：
= n/2 + (n/2)(log₂ n - 1) - αn/2 + (n/2)(log₂ n - 1) - O(n)
= n/2 + n log₂ n - n - αn/2 - O(n)
= n log₂ n - n/2 - αn/2 - O(n)。
比较两边：
- αn ≈ n/2 + αn/2 + O(n)
⇒ αn - αn/2 ≈ n/2
⇒ αn/2 ≈ n/2
⇒ α ≈ 1。
因此 C(n) ≈ n log₂ n - n + o(n)。
步骤 4.3：与信息论下界对比
排序的信息论下界为 log₂(n!) ≈ n log₂ n - n log₂ e + O(log n)。
由于 log₂ e ≈ 1.4427，而我们的 α = 1，故 Ford-Johnson 的比较次数 n log₂ n - n 比信息论下界 n log₂ n - 1.4427n 稍大，但已非常接近。
步骤 4.4：精确最坏情况比较次数
已知 Ford-Johnson 算法最坏比较次数为：
C(n) = n log₂ n - α(n) n + O(log n)，
其中 α(n) ∈ [1, 1.1] 且与 n 有关。
具体值由 Jacobsthal 顺序优化得到，当 n 为 2^k - 1 时，α(n) 接近 1。
5. 下界证明要点
要证明 C(n) ≥ n log₂ n - βn 对某个 β 成立：
- 利用决策树模型，叶子数至少 n!，因此树高 ≥ log₂(n!)。
- 但算法中比较次数可能少于树高？不，决策树高即最坏比较次数。
- 因此 C(n) ≥ ⌈log₂(n!)⌉。
- 而 ⌈log₂(n!)⌉ = n log₂ n - n log₂ e + O(log n)。
- 因此任何比较排序的下界即此，Ford-Johnson 的 C(n) 与之差一个线性项系数。
关键结论：Ford-Johnson 算法在最坏情况下的比较次数与信息论下界的差距仅为线性项系数不同，是渐进最优的比较排序算法之一。