lower bound · heapsort

比较排序的下界与 heapsort

quicksort 与自适应归并排序都在同一个前提下工作：算法获取信息的唯一途径是拿两个元素问一句「谁不比谁大」。这个前提本身就给出了一条谁也绕不过的底线。本页先把「一次比较能带来多少信息」形式化成一棵树，由树高推出 $\Omega(n \log n)$ ，再用穷举实测看各个算法离这条底线有多远，最后把 stable 与 in-place 两条正交的性质加进来，得到一张坐标系。

绕过底线的办法留给线性时间排序：那里的算法根本不问「谁不比谁大」。

1 · decision tree 模型

固定 $n$ ，把一个比较排序在所有输入上的行为画成一棵二叉树：内部节点是一次比较 $a_i \le a_j$ ，两条出边对应两种答案，叶子是算法最终给出的输出顺序。这棵树叫 decision tree。

模型能成立，靠的是一条不变量：走到同一节点的所有输入，此前得到的答案序列完全一致，算法无从区分它们，下一步只能问同一对位置。有了它，「树高」才等于「最坏情形的比较次数」。

本页的树不是手绘的示意图，而是跑出来的：枚举 $n!$ 种输入排列，每种都让插桩过的算法真跑一遍，记下它依次比较了哪两个输入位置以及结果，再按结果序列建 trie。上面那条不变量由 core/decision.test.ts 对四种算法、 $n \le 4$ 逐节点断言。

图 1-1 · 由实际执行构造的 decision tree。节点上的两个数字是被比较的输入位置，叶子是输出顺序，底部代码面板高亮出该算法获取信息的入口。可换元素个数、算法与输入排列，蓝色路径是当前输入走过的分支。

2 · 树高的下界

定理 2.1 任何基于比较的排序算法，在最坏情形下至少要做 $\lceil \log_2 n! \rceil$ 次比较。

证明算法必须能区分 $n!$ 种输入排列：两个不同排列若落到同一叶子，算法对它们给出的重排方式相同，至少有一个结果不是升序。故 decision tree 的叶子数不少于 $n!$ 。高为 $h$ 的二叉树叶子数不超过 $2^h$ ，两者合起来给出 $2^h \ge n!$ ，即 $h \ge \log_2 n!$ 。比较次数是整数，取上整；而 $h$ 按定义就是最坏情形走过的比较次数。∎

由 Stirling 公式 $\log_2 n! = n \log_2 n - n \log_2 e + O(\log n)$ ，这条底线的量级是 $\Theta(n \log n)$ 。它不针对任何具体算法，只针对「靠比较获取信息」这一件事。

平均情形也逃不掉。 $n!$ 个叶子的二叉树里，外部路径长度最小的形态是尽量平衡的那一棵，其叶子平均深度不低于 $\log_2 n!$ 。所以随机排列上的期望比较次数同样是 $\Omega(n \log n)$ 。

3 · 小规模输入上的实测

渐近式看不出常数。把 $n$ 从 2 取到 8、穷举每个 $n$ 的全部 $n!$ 种输入，就能量出各算法的最坏比较次数，与 $\lceil \log_2 n! \rceil$ 并排放。

$n = 8$ 时底线是 16 次。binary insertion sort 与 merge sort 各要 17 次，只多一次；insertion sort、selection sort 与 quicksort 各 28 次；heapsort 29 次。heapsort 是这张表里离底线最远的一个， $n = 8$ 上甚至比 selection sort 还多一次。它的 $O(n \log n)$ 最坏保证是渐近意义上的，小规模输入里的常数并不占便宜。

$n \le 4$ 时 binary insertion sort 与 merge sort 都正好压在底线上（ $n = 4$ 时底线 5，两者都是 5）。从 $n = 5$ 起两者都差一次，那一格要 Ford–Johnson 的 merge insertion 才补得上 [3]。

注 · binary insertion sort 的比较次数并非与输入无关。常见说法是它恒为 $\sum_{i=2}^{n} \lceil \log_2 i \rceil$ ，写完 core/sorts.ts 后枚举 $n = 6$ 的全部 720 个排列，实测落在 8 到 11 之间，四种取值都出现。原因在 lower_bound 的区间长度不是 2 的幂时会提前收敛，少比一次。恒定的只有那个上界。这条断言由 core/sorts.test.ts 钉住。

图 3-1 · 穷举

n!

种输入量出的最坏比较次数与信息论底线的对照。可逐格前进看

n

从 2 走到 8，达到底线的条目标绿。

4 · stable 与输出的可辨识性

一个排序是 stable 的，指键相同的元素排完后仍保持它们在输入里的先后。这条性质在 decision tree 里看不见：算法只能问键的大小，问不到「谁来自更靠前的位置」。它由搬移方式决定，不由比较次数决定。

最小的反例只要三个元素。输入 2 2 1，selection sort 找出最小的 1 并与首位对调，两个 2 的先后当场颠倒。凡是会跨距离交换元素的排序（selection sort、heapsort、quicksort 的分区）都有同样的风险；只在相邻元素之间搬移的排序则天然保序。merge sort 的稳定性集中在一行上：两段头部相等时取左段。

图 4-1 · 键相同的元素在排序中是否被换序。柱高是键，下方字母是它在输入里的位置，末帧把被换序的相邻对标出来。可换算法与输入。

下一页会看到，stable 不只是排序结果好不好看的问题：radix sort 的每一趟都必须 stable，否则高位排好的次序会被低位那一趟抹掉。

5 · 排序算法的坐标系

把最坏比较次数、额外空间与 stable 三项摆在一起，各个算法的位置就清楚了。

算法	最坏比较次数	额外空间	stable
insertion sort	$\Theta(n^2)$	$O(1)$	是
binary insertion sort	$\Theta(n \log n)$ 次比较、 $\Theta(n^2)$ 次搬移	$O(1)$	是
selection sort	$\Theta(n^2)$	$O(1)$	否
merge sort	$\Theta(n \log n)$	$\Theta(n)$	是
heapsort	$\Theta(n \log n)$	$O(1)$	否
quicksort（末位 pivot）	$\Theta(n^2)$	$O(\log n)$ 递归栈	否
introsort	$\Theta(n \log n)$	$O(\log n)$ 递归栈	否
Timsort	$\Theta(n \log n)$	$O(n)$	是

「最坏 $\Theta(n \log n)$ 」与「额外空间 $O(1)$ 」这两格同时成立的，表里只有 heapsort 一个。这就是它在下界这条线上的位置：底线说最坏至少 $\log_2 n!$ 次比较，heapsort 在渐近意义上达到了，而且没有借助任何辅助数组。称一个排序 in-place，指它的额外空间是 $O(1)$ ，与 $n$ 无关。

代价写在另外两栏。heapsort 不 stable；它的缓存局部性也差，sift-down 每下一层就跳到约两倍远的下标，与 merge sort 的顺序扫描不在一个量级上。这两点加上 §3 那个偏大的常数，正好解释了为什么标准库很少直接用它，而是把它留给 quicksort 的深度兜底。sift-up 与 sift-down 的机制见 binary heap。

merge sort 那个 $\Theta(n)$ 的辅助数组并非无法消除。 $O(1)$ 额外空间的稳定归并算法确实存在 [4]，但常数大到实用实现罕见；Timsort 走的是折中路线，缓冲只取两段中较短的那一段。

6 · 参考文献

Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.). Addison-Wesley, §5.3.1.
Williams, J. W. J. (1964). Algorithm 232: Heapsort. Communications of the ACM, 7(6), 347–348.
Ford, L. R., & Johnson, S. M. (1959). A tournament problem. The American Mathematical Monthly, 66(5), 387–389.
Katajainen, J., Pasanen, T., & Teuhola, J. (1996). Practical in-place mergesort. Nordic Journal of Computing, 3(1), 27–40.