Quicksort，需要
heapsort，需要
merge sort，需要
insertion sort，需要
在前幾天的時間我們看到了這一些演算法，我們發現他們最快時間都在，那有沒有可能有一個演算法它的速度是快過於
的?
我們會發現這上面四種排序的演算法都有一個性質，就是透過比較兩個元素的大小關係來做出排序，也就是它們是基於同樣的一種演算法模型去設計的演算法，而在這個演算法模型底下，是我們能夠達到的最快速度。
在這個演算法模型中，規範了我們能夠對兩個元素a和b進行怎樣的操作，像是我們可以執行,
,
,
,
這些操作，如果我們對整數集合進行排序，我們只能對元素進行比較的操作，不能做出相加，相乘等等在這個演算法模型規範以外的操作。
關於透過比較方式進行的排序，我們可以使用決策樹來表示他，決策樹是一顆完全二元樹，他可以表示給定固定大小的輸入，產生出所有可能排序情況。
假設給定陣列
從樹根開始看，比較和
，
如果，就
和
進行比較。
如果，就
和
進行比較。
給定陣列，我們想要產生出由小到大的排列，整個決策樹的走法如下
最終產生出的組合為(3,1,2)，即為由小到大的排列方式。
在決策樹中，每一個內部節點都是以標記，其中
，
維陣列中元素的個數。每個內部節點會分出兩顆子樹，左子樹表示
所需要進行的後續比較，右子樹表示
所需要進行的後續比較。對於一個正確的比較排序演算法，
個元素的陣列會產生出
種排列的情況，也就是產生出
個葉節點。
上面提及的四種演算法都可以使用決策樹的方式進行表示，但一般來說不會那麼做，原因為考慮一般性，也就是考慮排序長度為的陣列，會有
個節點，導致樹長的非常大一棵，因此一般描述演算法時會採用虛擬碼的方式進行描述。
使用決策樹的好處，在於我們可以直觀的分析對於長度為的陣列，排序所需要的執行時間與最差情況。
從樹根到任一葉節點之間的路徑長度，表示排序演算法所需要進行比較的次數，也就是執行時間，可以表示成樹的深度。而最壞情況就是樹根到葉節點最長的路徑長度，也就是樹的高度，有最多的比較次數。
我們要證明在這個比較模型底下，沒有任何一種演算法是要比還要快的，也就是最長路徑的最小值為
證明: 對於長度為n的陣列所繪製出的決策樹，其樹高為
對於長度為n的陣列所繪製出的決策樹，其擁有個節點，令決策樹的高度為
，葉子數量為
，則最多擁有
個葉節點，因為這是一棵二元樹，每個節點都有兩個分支，因此我們可以得出下面關係式
，對兩邊式子取對數
(因為
為單調遞增函數，因此可以做這樣的操作)
根據Stirling's formula，用來取
的近似值
，
和
為常數，當n趨近於無限時可以忽略不計
結論: 對於使用比較大小方式進行排序的演算法，皆可以對應到決策樹，並且效率都不會好過於，而heapsort,merge sort和隨機化的quicksort他們執行時間的上界為
，恰好對應到決策樹的下界。隨著n的增長，heapsort,merge sort隨機化的quicksort會漸進式的趨近於在決策樹模型下的最優解，也就是貼近他的下界。
線性時間幾乎是我們可以得到的最有效率結果(不考慮平行化處理或是一些情況)，因為我們至少需要遍歷過整個數據。
如何在線性時間內完成排序，要突破模型的限制，就是我們不在比較元素的大小，對元素做其他的操作，也就是讓這個演算法不被這個模型所包含，那這個演算法就有機會達到線性時間內的排序了。
參考資料:Introduction to algorithms 3rd
iThome鐵人賽
看影片追技術