CBA理论, 为什么基于比较的排序方法的性能极限是O(nlogn)

缘起

排序是计算机科学中的基础算法, 很多算法，譬如图算法等都基于排序算法. 所以弄清楚排序算法的性能极限是很重要的. 很多排序——快排、堆排、归并、胜者树等基于比较的排序算法的性能都是O(nlogn). 其实

CBA（comparison-based-algorithm）理论： 任何基于比较的排序算法的性能天花板就是O(nlogn)

分析

原因很简单, n个元素的全排列是n!. 而最终排序的结果只是其中一种（一棵含有n!个叶子节点的二叉树）. 每次比较, 我们可以砍掉一半的元素. 所以比较的次数就是树的高度.而此树的高度是
$$
\log_2n!
$$
由分析数学中的Stirling公式便知.速度不可能突破NlogN.