Sorting

基于比较的确定性算法有时间复杂度下界$O(n\log n)$，该证明的思路是简单的：考虑基于比较地给一个全排列$\sigma$排序，第一次比较$\sigma_{i_1},\sigma_{j_1}$两个元素。$\sigma$分为两类，一类满足$\sigma_{i_1}<\sigma_{j_1}$，一类满足$\sigma_{i_1}>\sigma_{j_1}$；在每一类中，又可以分为$\sigma_{i_2}<\sigma_{j_2}$和$\sigma_{i_2}>\sigma_{j_2}$。如果把这种分类看成一颗二叉树的话，它的叶节点就有$n!$个。排序算法的优劣就在于怎么选择每一次的$i_k,j_k$，因为这决定了二叉树的形态。为了让排序算法最优秀，应当让最坏的也就是深度最大的叶节点的深度尽量小。因此这应当尽量是一颗平衡树，此时最大深度为$\log_2 (n!)$。根据Stirling's Formula，$n! \sim \sqrt{2n\pi}\left(\dfrac{n}{e}\right)^n$，因此$O(\log n!)=O(n \log n)$。可见任何基于比较的排序算法都有复杂度下界$O(n \log n)$。

基于比较的排序算法是没有利用数字本身的信息的，这类算法称为ordinal的。利用数字本身信息的算法称为cardinal的。考虑以下经典的整数排序问题：给$n$个数排序，每个数都在集合$\{0,1,2,\cdots,m-1\}$中。下面我们给出一个整数排序问题的确定性算法，复杂度为$O(n\log\log n)$且只需要线性空间。（通过引入随机性，随机算法可以做到期望时间$O(n\sqrt{\log\log n})$和线性空间解决整数排序。）