基于比較排序的算法的性能是有上限的，大部分人都知道是nlgn，但是為什么多年的研究都突破不了nlgn呢，其實數(shù)學(xué)早已給出了答案。

每一種基于比較的排序算法，都可以看作一棵二叉排序樹，葉子節(jié)點代表每一種排序結(jié)果，算法的不同就體現(xiàn)在構(gòu)造這棵樹的不同方法。葉子到樹根的距離表示比較次數(shù)，也就是時間。由二叉樹的性質(zhì)，2^h>=k，k為葉子節(jié)點，且所有的排序結(jié)果有n!個，所以h>=lg(n!)，即T(n)>=lg(n!)，由斯特林公式，可以得到，T(n)>=O(nlgn)，或者近似地看，lg(n!)=lgn+lg(n-1)+…+lg1，復(fù)雜度就是nlgn，這便是問題所在。

但是不論是什么排序算法，都不可能小于O(n)，因為你至少每個元素看一眼都是線性時間。又因為上次說到，lgn接近常數(shù)級，所以nlgn的排序算法已經(jīng)很優(yōu)秀了。

同為nlgn，為什么快排的性能要優(yōu)于歸并排序呢，這是因為除了比較，還有一個開銷便是搬動元素，歸并排序需要大量讀入寫出，而快排只需要把比pivot大的向后挪就行了。但是歸并排序很適合外部排序，因為一次將兩個隊首元素讀入就OK了。