基于比较排序的算法的性能是有上限的，大部分人都知道是nlgn，但是为什么多年的研究都突破不了nlgn呢，其实数学早已给出了答案。

每一种基于比较的排序算法，都可以看作一棵二叉排序树，叶子节点代表每一种排序结果，算法的不同就体现在构造这棵树的不同方法。叶子到树根的距离表示比较次数，也就是时间。由二叉树的性质，2^h>=k，k为叶子节点，且所有的排序结果有n!个，所以h>=lg(n!)，即T(n)>=lg(n!)，由斯特林公式，可以得到，T(n)>=O(nlgn)，或者近似地看，lg(n!)=lgn+lg(n-1)+…+lg1，复杂度就是nlgn，这便是问题所在。

但是不论是什么排序算法，都不可能小于O(n)，因为你至少每个元素看一眼都是线性时间。又因为上次说到，lgn接近常数级，所以nlgn的排序算法已经很优秀了。

同为nlgn，为什么快排的性能要优于归并排序呢，这是因为除了比较，还有一个开销便是搬动元素，归并排序需要大量读入写出，而快排只需要把比pivot大的向后挪就行了。但是归并排序很适合外部排序，因为一次将两个队首元素读入就OK了。