排序到底能有多快？

比較排序的下界

比較排序了解資料的唯一途徑是問"a 是否小於 b？"。令人意外的是，僅憑這個問題就限制了任何此類排序能有多快：沒有任何比較排序能在最壞情況下突破 Ω(n log n)。因此合併排序和調校良好的快速排序在比較排序中本質上已是最優。

直覺是一棵決策樹。每次比較有兩種結果，所以高度為 h 的是非答案樹至多能區分 2^h 種情形。要排好 n 個元素，你必須分辨全部 n! 種可能的排列，於是需要 2^h ≥ n!，即 h ≥ log2(n!)。而 log2(n!) 的增長形如 n log n——這就是那道牆，無需繁重的證明。

Decision tree to sort 3 elements a, b, c (each leaf = one ordering):

                a<b ?
              /       \
           yes          no
          b<c?          a<c?
         /    \        /    \
     a<b<c   a<c?   b<a<c   b<c?
            /   \          /   \
        a<c<b  c<a<b   b<c<a  c<b<a

  3! = 6 leaves -> tree must be tall enough; height ~ log2(6).

不靠比較，越過這道牆

這道牆只約束比較型排序。如果你改為把鍵本身當作索引，就能逃出它。計數排序對範圍在 0..k 內的 n 個整數排序：統計每個值出現的次數，再按順序寫出來——O(n + k)，完全不做比較。

// counting sort for values in [0, k]
void countingSort(int a[], int n, int k) {
    std::vector<int> count(k + 1, 0);
    for (int i = 0; i < n; i++) count[a[i]]++;   // tally each value
    int idx = 0;
    for (int v = 0; v <= k; v++)                 // write back in order
        while (count[v]-- > 0) a[idx++] = v;
}

堆積排序：原地的 O(n log n)

在比較排序中還有一個值得認識：堆積排序。它從陣列建出一個堆積（一種樹形的優先級結構，你將在下一級見到），然後反覆取出最大值並縮小堆積。它是最壞 O(n log n)——與合併排序的保證相當——而且原地進行，只用 O(1) 額外空間。

1. 合併排序：永遠 O(n log n)，穩定，O(n) 空間。
2. 快速排序：平均 O(n log n) / 最壞 O(n^2)，不穩定，原地，實踐中最快。
3. 堆積排序：最壞 O(n log n)，不穩定，原地——以 O(1) 空間換取最壞情況保證。
4. 計數 / 基數排序：O(n + k) / O(d·(n+基數))，但僅限小整數鍵。

把它們串起來

所以"排序能有多快？"有兩個答案。如果你只能比較，Ω(n log n) 就是地板，合併/快速/堆積排序正好踩在上面。如果你的鍵有結構——小整數——你就能改用計數而非比較，降到線性時間。

下一級我們告別線性資料：展開到樹、為堆積排序提供動力的堆積，以及圖——而遞迴會一路同行。