比較排序下界（comparison-sorting lower bound）
合併排序與堆積排序都跑 O(n log n)，而幾十年來沒人找到根本上更快的比較排序。比較排序下界解釋了這不是運氣不好：它證明任何「靠比較鍵值來排序」的演算法，在最壞情況下都得做 Omega(n log n) 次比較。我們熟悉的 O(n log n) 排序不只是好；它們在自己的模型裡基本上就是最優的。
證明是一個簡短而優美的計數論證，用的是決策樹模型。排序 n 個相異元素，等於要判定 n! 種可能順序中哪一個才是真的。把演算法想成一棵二元決策樹：每個內部節點是一次比較，每片葉子宣布一個順序。要正確，n! 種順序每一個都得出現在某片葉子上，所以樹至少有 n! 片葉子。一棵有 L 片葉子的二元樹，樹高至少 log2(L)。因此最壞情況比較次數——樹高——至少是 log2(n!)。最後，由史特靈估計，log2(n!) 約為 n log2(n) - 1.44 n，亦即 Theta(n log n)。所以樹高 >= log2(n!) = Omega(n log n)，這就是下界。
兩點澄清讓它保持誠實。第一，此界只對比較模型成立：計數排序、基數排序與桶排序可以跑 O(n)，因為它們利用了鍵值的實際數值或位數，跳出了比較——它們沒有反駁定理，只是離開了它的競技場。第二，這是對比較次數的「最壞情況」下界；某些特定輸入（餵給插入排序的已排序陣列）可以便宜得多，而此界對那些簡單情形隻字未提。由於上界 O(n log n) 與此下界 Omega(n log n) 重合，比較排序是少數複雜度被完全釘死的問題之一：Theta(n log n)。
對 n = 4，有 4! = 24 種順序，所以任何比較排序的決策樹都需要 >= 24 片葉子，樹高 >= ceil(log2(24)) = 5。確實沒有比較排序能永遠用 4 次比較排好 4 個元素；最壞情況需要 5 次。這個計數論證精準預測了那塊地板。
n! 種順序逼出 n! 片葉子；有那麼多葉子的二元樹至少 log2(n!) = Omega(n log n) 那麼高。
它並沒有說排序永遠需要 n log n 步——只說比較排序、只在最壞情況。線性時間排序（基數、計數）是真實且正確的；它們只是不靠比較鍵值運作，所以在定理之外。