進階排序：O(n log n) 排序演算法#

歸併排序與快速排序是處理大規模資料的主力演算法，兩者都運用分治思想，但策略截然不同。

分治思想#

將大問題分解為小問題，解決小問題後合併結果。

flowchart TB
    subgraph 歸併排序["歸併排序：由下而上"]
        direction TB
        M1[分解陣列] --> M2[遞迴排序左半]
        M1 --> M3[遞迴排序右半]
        M2 --> M4[合併結果]
        M3 --> M4
    end

    subgraph 快速排序["快速排序：由上而下"]
        direction TB
        Q1[選擇 Pivot] --> Q2[分區操作]
        Q2 --> Q3[遞迴排序左區]
        Q2 --> Q4[遞迴排序右區]
    end

    style M4 fill:#e8f5e9
    style Q2 fill:#fff3e0

T(n) = 2*T(n/2) + O(n)  =>  T(n) = O(n log n)

比較排序的下界：為什麼快不過 O(n log n)#

歸併與快排都屬於比較排序——它們判斷元素順序的唯一手段，是把兩個元素拿來比大小。這類演算法存在一道無法跨越的牆：最壞情況至少要 O(n log n) 次比較。理由很單純：

1. n 個元素一共有 n! 種可能的排列。排序的本質，就是在這 n! 種可能裡，找出輸入到底是哪一種。
2. 每做「一次兩兩比較」，結果只有「大於」或「不大於」兩種，最多帶來 1 bit 的資訊量。
3. 要從 n! 種可能中唯一確定一種，至少需要 log₂(n!) bit 的資訊，也就是至少 log₂(n!) 次比較。
4. 由 Stirling 近似，log₂(n!) ≈ n log n。所以任何比較排序的下界都是 O(n log n)。

換句話說，歸併排序已經打到了這道牆的底部——它不是「剛好」是 O(n log n)，而是在比較模型下已經最優。這也呼應了找下界的思維：先知道「最好能多快」，才知道手上的解還有沒有優化空間。關於下界這個觀念的完整展開，見複雜度的下界。

log₂(n!) = log₂(1) + log₂(2) + ... + log₂(n) = Σ log₂(i)

Σ_{i=1}^{n} log₂(i) ≈ ∫_{1}^{n} log₂(x) dx
                    = (n ln n − n) / ln 2
                    ≈ n log₂(n) − 1.44 n

n! ≈ √(2πn) · (n / e)^n

歸併排序 (Merge Sort)#

由下而上：先遞迴處理子問題，再合併結果。

核心流程#

1. 將陣列從中間分成兩半
2. 對左右兩半分別遞迴排序
3. 合併兩個有序陣列

fun mergeSort(arr: List<Int>): List<Int> {
    if (arr.size <= 1) return arr

    val mid = arr.size / 2
    val left = mergeSort(arr.subList(0, mid))
    val right = mergeSort(arr.subList(mid, arr.size))
    return merge(left, right)
}

private fun merge(left: List<Int>, right: List<Int>): List<Int> {
    val result = ArrayList<Int>(left.size + right.size)
    var i = 0
    var j = 0
    while (i < left.size && j < right.size) {
        if (left[i] <= right[j]) {  // <= 保證穩定性
            result.add(left[i])
            i++
        } else {
            result.add(right[j])
            j++
        }
    }
    while (i < left.size) result.add(left[i++])
    while (j < right.size) result.add(right[j++])
    return result
}

歸併排序的空間複雜度是 O(n) 而非 O(n log n)。雖然遞迴層數是 log n，但同一時間只有一個函式在執行，臨時空間會被釋放重用。

快速排序 (Quick Sort)#

由上而下：先分區，再遞迴處理子問題。

核心流程#

1. 選擇一個 pivot（分區點）
2. 將小於 pivot 的放左邊，大於 pivot 的放右邊
3. 對左右兩部分遞迴排序

fun quickSort(arr: IntArray, low: Int = 0, high: Int = arr.size - 1): IntArray {
    if (low < high) {
        val pivotIdx = partition(arr, low, high)
        quickSort(arr, low, pivotIdx - 1)
        quickSort(arr, pivotIdx + 1, high)
    }
    return arr
}

private fun partition(arr: IntArray, low: Int, high: Int): Int {
    val pivot = arr[high]  // 選最後一個元素作為 pivot
    var i = low
    for (j in low until high) {
        if (arr[j] < pivot) {
            val tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp
            i++
        }
    }
    val tmp = arr[i]; arr[i] = arr[high]; arr[high] = tmp
    return i
}

快排最佳化策略#

問題：最壞情況 O(n²)#

當資料已有序且每次選最後一個元素作為 pivot 時，分區極度不均衡。

解決方案#

1. 三數取中法：取首、中、尾三個數的中位數作為 pivot
2. 隨機法：隨機選擇 pivot，降低最壞情況發生的概率
3. 避免遞迴過深：設定遞迴深度閾值，或使用堆上的堆疊模擬遞迴

快排 vs 歸併

比較項目	歸併排序	快速排序
時間穩定性	穩定 O(n log n)	平均 O(n log n)，可能退化
空間複雜度	O(n)	O(log n)
實際應用	較少（記憶體消耗大）	較多（原地、常數項小）

問題：大量相等元素#

除了「已排序輸入」之外，還有一個常被忽略的陷阱：陣列裡有大量相等的元素。前面 partition 那種「只把小於 pivot 的往左換」的單向掃描，遇到一堆等於 pivot 的元素時，會把它們全部堆到同一側，分區再次極度不均衡，又退化成 O(n²)。

解法是改用雙向掃描：左指標從頭找「不小於 pivot」的、右指標從尾找「不大於 pivot」的，兩邊都停下時交換。關鍵在於遇到等於 pivot 的元素也照樣停下、照樣交換——這樣相等元素會被平均分到兩側，分區重新變得均衡。（更進一步的做法是「三路分區 / Dutch National Flag」，直接把陣列分成 < pivot、= pivot、> pivot 三段，等於 pivot 的那段不再遞迴。）

先選對演算法，再談微調

這些調校的層次感很重要：換演算法帶來的是「數量級」的差距（O(n²) ➡️ O(n log n)，資料一大就是天壤之別）；而 pivot 選法、小區間切插入排序這類 code tuning，通常只帶來 2~4 倍的常數改善。所以面對效能問題，永遠先確認「演算法選對了嗎」，把數量級拿到手，再回頭做這些微調——順序反過來，往往是事倍功半。

經典應用：O(n) 查找第 K 大元素#

利用快排的分區思想，可以在 O(n) 時間內找到無序陣列中的第 K 大元素 ^↗，這個技巧稱為 quickselect。

fun findKthLargest(arr: IntArray, k: Int): Int {
    var low = 0
    var high = arr.size - 1
    while (low <= high) {
        val pivotIdx = partitionDesc(arr, low, high)
        when {
            pivotIdx == k - 1 -> return arr[pivotIdx]
            pivotIdx < k - 1  -> low = pivotIdx + 1
            else              -> high = pivotIdx - 1
        }
    }
    return -1
}

private fun partitionDesc(arr: IntArray, low: Int, high: Int): Int {
    val pivot = arr[high]
    var i = low
    for (j in low until high) {
        if (arr[j] >= pivot) {  // 降序分區
            val tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp
            i++
        }
    }
    val tmp = arr[i]; arr[i] = arr[high]; arr[high] = tmp
    return i
}

為何是 O(n)？每次只需處理一半：n + n/2 + n/4 + … = 2n = O(n)

突破下界：不靠比較就能更快#

前面說過，只要靠兩兩比較，就逃不掉 O(n log n) 這道牆。但這道牆有一個關鍵前提——「靠比較」。一旦換掉這個前提，下界就不再適用，於是出現了兩條繞過它的路。

路徑一：用值本身當索引（不做比較）#

計數排序、桶排序、基數排序之所以能達到 O(n)，正是因為它們根本不做兩兩比較：它們直接拿元素的值（或其某個位數）當作陣列索引去歸位。沒有比較，就沒有「每次最多 1 bit」的限制，自然不受 log₂(n!) 約束。代價是它們對輸入有額外假設（值域有限、可當索引），這也是為什麼它們不是通用排序。詳見線性排序。

路徑二：根本不排序整個陣列#

用 partition 找「第 K 大 / 中位數」（前一節）能達到 O(n)，也是同一層道理：它不需要把整個陣列排好。比較排序的下界，講的是「完整排序」這件事；但若你只想知道第 K 個位置的元素，每次分割後只要往含目標的那一半繼續找，另一半直接丟掉。期望計算量是 N + N/2 + N/4 + … ≈ 2N，故 O(n)——比「先排序再取第 K 個」的 O(n log n) 整整快一個數量級。

下界不是「演算法的天花板」，而是「問題模型的天花板」。想突破它，不要硬優化既有解法，而要回頭問：我是不是被困在「比較」「完整排序」這些不必要的前提裡？換掉問題模型，牆就消失了。

混合排序：工業界真正在用的排序#

教科書講的「純」歸併、純快排，跟標準庫實際在用的排序之間有不小落差。真實世界的標準庫幾乎都用混合排序（hybrid sort）——把多種演算法的優點縫在一起，針對真實資料的特性（常常局部有序、常含重複）做工程取捨。

兩個最具代表性的方案：

• Timsort：Python 內建 sort、Java 的物件陣列排序、Android 都用它。它先掃描資料，找出其中天然存在的遞增 / 遞減連續區段（run）；短的 run 用插入排序補齊到一定長度，再用一套有規則的策略聰明地合併這些 run。對「本來就接近有序」的真實資料特別快，最壞仍是 O(n log n)，而且穩定。
• Introsort（introspective sort）：C++ STL 的 std::sort 用它。它以快排為主，但會監看遞迴深度——一旦遞迴過深（代表 pivot 一直選得很糟，快要退化成 O(n²)），就切換成堆排序收尾。如此一來，平均享受快排的常數小、原地的優點，最壞情況又被堆排序的 O(n log n) 兜住。

兩者的共通哲學都是「不賭單一演算法」：用一個常數小、對常見輸入快的主力，再配一個保底機制接住最壞情況。這正是工業級程式碼與教科書範例最大的差異所在。

工業級排序函式實作（以 C 語言 qsort 為例）#

1. 小資料量：使用歸併排序（空間換時間可接受）
2. 大資料量：使用快速排序
3. 分區點選擇：三數取中法
4. 遞迴最佳化：堆上模擬堆疊，避免堆疊溢出
5. 小區間最佳化：元素 <= 4 時切換為插入排序