排序算法之：基于“最小比较数排序”（Ford-Johnson Merge Insertion Sort）的递推关系与比较次数下界分析

我将为您讲解一个在比较排序理论中具有重要地位的算法——Ford-Johnson Merge Insertion Sort（通常称为“合并插入排序”或“最小比较数排序”）。这个算法以其接近理论下界的比较次数而闻名。让我们循序渐进地探讨其递推关系和比较次数下界。

算法概述

Ford-Johnson算法是一种基于比较的排序算法，由Lester R. Ford和Selmer M. Johnson于1959年提出。它的核心目标是在对n个元素进行排序时，尽可能减少比较的次数。虽然其时间复杂度仍然是O(n²)（因为移动操作多），但在比较次数上，它对于n≤15的情况是最优的，并且在理论上，其比较次数非常接近信息论下界⌈log₂(n!)⌉。

解题过程详解

步骤1：理解算法的基本思想

算法的核心思想是：

1. 成对比较：首先将所有元素两两比较，形成一组“优胜者”和一组“失败者”。
2. 递归排序：对优胜者递归排序。
3. 二分插入：将失败者按照特定顺序插入到已排序的优胜者序列中，利用二分查找减少比较次数。

这个插入顺序是关键——它确保每个失败者插入时，只需要与尽可能少的已排序元素比较。

步骤2：算法的详细步骤

让我们以具体例子说明。假设要排序数组 [5, 2, 8, 3, 1, 6, 4, 7]，n=8。

阶段1：成对比较与分组

• 将元素两两分组比较：(5,2), (8,3), (1,6), (4,7)
• 记录每组中的较小者（失败者）和较大者（优胜者）：
  • 组1: 优胜者5，失败者2
  • 组2: 优胜者8，失败者3
  • 组3: 优胜者6，失败者1
  • 组4: 优胜者7，失败者4
• 现在我们有：
  • 优胜者序列 W = [5, 8, 6, 7]（未排序）
  • 失败者集合 L = {2, 3, 1, 4}（记住对应关系）

阶段2：递归排序优胜者

• 对W递归应用相同的算法（当n≤3时，可用简单排序）：
  • 比较5和8 → 5<8
  • 比较6和7 → 6<7
  • 比较两组优胜者：5和6 → 5<6
  • 最终排序后的优胜者序列：W_sorted = [5, 6, 7, 8]

阶段3：失败者的插入顺序
这是最精妙的部分。我们不是按失败者原顺序插入，而是按照一种特殊顺序，使得每次插入时的比较次数最小。

插入顺序由Jacobsthal数决定。对于n=8，我们需要将失败者按特定顺序插入：

1. 首先插入第一个失败者（对应最小优胜者）：

   • 从W_sorted中找到对应最小优胜者5的失败者是2
   • 将2插入到已排序序列（目前只有[5]）→ 通过二分查找插入位置
   • 结果序列：[2, 5, 6, 7, 8]

2. 然后按特定顺序插入其他失败者：

   • 顺序由一种特殊模式决定：首先插入对应位置3、5、2、4的失败者（这是由Jacobsthal数导出的）
   • 实际插入顺序：对应优胜者6的失败者1 → 对应优胜者7的失败者4 → 对应优胜者8的失败者3
   • 每次插入都使用二分查找确定位置

最终得到完全排序的序列。

步骤3：递推关系推导

设F(n)表示用Ford-Johnson算法排序n个元素所需的最坏情况比较次数。

递推关系如下：

1. 当n=1时，F(1)=0
2. 当n=2时，F(2)=1
3. 对于n>2：
   • 第一步：将元素两两比较，需要⌊n/2⌋次比较
   • 第二步：递归排序⌈n/2⌉个优胜者，需要F(⌈n/2⌉)次比较
   • 第三步：插入⌊n/2⌋个失败者
     • 第一个失败者插入时，最多需要比较⌈log₂(1)⌉=0次？实际需要比较1次
     • 后续失败者按特定顺序插入，第j个失败者插入时，最多需要比较⌈log₂(j+1)⌉次

因此，递推公式为：

F(n) = ⌊n/2⌋ + F(⌈n/2⌉) + Σ_{j=1}^{⌊n/2⌋} ⌈log₂(3j/2)⌉

更精确的公式是：

F(n) = F(⌈n/2⌉) + F(⌊n/2⌋) + G(⌈n/2⌉, ⌊n/2⌋)

其中G(m,k)表示将k个失败者插入m个已排序优胜者中所需的最少比较次数。

步骤4：比较次数下界分析

信息论告诉我们，任何基于比较的排序算法至少需要⌈log₂(n!)⌉次比较。

Ford-Johnson算法的比较次数F(n)与这个下界的比值如何？

通过计算小n值的情况：

• n=3: F(3)=3, 下界⌈log₂(3!)⌉=⌈2.585⌉=3 → 最优
• n=4: F(4)=5, 下界⌈log₂(4!)⌉=⌈4.585⌉=5 → 最优
• n=5: F(5)=7, 下界⌈log₂(5!)⌉=⌈6.907⌉=7 → 最优
• n=12: F(12)=30, 下界⌈log₂(12!)⌉=29 → 只多1次

事实上，Ford-Johnson算法在n≤15时是最优的，对于更大的n，其比较次数与下界的差距也很小：

F(n) = n⌈log₂ n⌉ - 2^{⌈log₂ n⌉} + 1 （近似公式）

与下界⌈log₂(n!)⌉ ≈ n log₂ n - 1.443n 相比，Ford-Johnson算法的比较次数大约多出0.1n左右。

步骤5：算法的时间复杂度与实用性

虽然Ford-Johnson算法在比较次数上接近最优，但它的时间复杂度仍然是O(n²)，因为：

1. 移动操作很多：每个插入都可能需要移动大量元素
2. 实现复杂：需要维护优胜者-失败者的对应关系
3. 缓存不友好：频繁的内存移动

因此，在实际应用中，它很少被使用。快速排序、归并排序等虽然比较次数稍多，但实际运行更快，因为：

• 它们有更好的缓存局部性
• 移动操作更少
• 实现更简单

关键点总结

1. 成对比较先行：先两两比较，分出优胜者和失败者
2. 递归排序优胜者：对优胜者递归应用相同算法
3. 智能插入失败者：按Jacobsthal数确定的特殊顺序插入失败者，最大化二分查找效率
4. 递推关系：F(n) = ⌊n/2⌋ + F(⌈n/2⌉) + Σ⌈log₂(3j/2)⌉
5. 接近最优：比较次数非常接近理论下界⌈log₂(n!)⌉，在n≤15时是最优的
6. 理论价值高：展示了比较排序可以达到多接近信息论下界
7. 实际限制：由于移动操作多、实现复杂，实际应用有限

这个算法的重要性在于它从理论上证明了比较排序可以多么接近信息论下界，为排序算法的理论研究提供了重要参考。虽然不实用，但它的设计思想——特别是通过精心安排的插入顺序来最小化比较次数——对算法设计有启发意义。