线性时间排序

排序算法时间的下界

决策树模型：比较排序可以被抽象地视为决策树

最坏情况下界：在决策树中， 从根到任意一个可达叶结点之间最长路径的长度，表示对应的排序算法中最坏情况下的比较次数。

任意一个比较排序算法在最坏情况下，都需要做Ω(nlgn）次的比较

堆排序和合并排序都是渐近最优的比较排序算法