形式陈述

在只允许比较两个键、输入含 $n$$n$ 个互异键的确定性比较排序模型中，算法可表示为二叉决策树：每个内部结点是一项比较，每个叶结点对应一种可能的相对次序。正确算法至少需要 $n!$$n!$ 个叶子，因此最坏比较次数 $h$$h$ 满足

$$ 2^h\ge n!, \qquad h\ge\lceil\log_2(n!)\rceil=\Omega(n\log n). $$$$2^h\ge n!,h\ge \lceil {\log }_2(n!)\rceil =\mathrm{\Omega }(n\log n).$$

由 Stirling 公式可得 $\log_2(n!)=n\log_2n-\Theta(n)$${\log }_2(n!)=n{\log }_{2}n-\mathrm{\Theta }(n)$。当输入在全部排列上均匀随机时，期望比较次数也有同阶下界。

直觉

一次二元比较最多提供一比特分支信息，而排序必须从 $n!$$n!$ 种可能顺序中确定一种；信息需求迫使树深至少是排列数的对数。

例子与边界

归并排序和堆排序的 $O(n\log n)$$O(n\log n)$ 比较数在渐近阶上最优。计数排序、基数排序可利用整数取值范围或数字表示绕过比较模型，因此不违反下界。存在重复键时叶子数可减少，但对所有互异输入的子集仍足以给一般最坏下界。

推论与应用

决策树计数是算法下界的基本模板，也用于选择、搜索和几何判定。它说明改进通用比较排序只能优化常数、缓存行为或适应性，不能把最坏比较数降到 $o(n\log n)$$o(n\log n)$。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Part I, comparison sorting and decision-tree lower bound。
• Donald E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed., Addison-Wesley, 1998，Vol. 3, §5.3.1, minimum comparison counts for sorting。