排序（二）：合併排序與快速排序

合併排序：永遠 O(n log n)

合併排序一字不差地套用分治：把陣列對半拆開，遞迴排好每一半，再合併兩個有序半段。拆分大約有 log2(n) 層，每層合併做 O(n) 的工作，於是在任何情況下都是 O(n log n)——最好、平均、最壞皆然。

核心是合併步驟：給定兩段有序序列，反覆取出較小的那個隊首元素。它需要一個大小為 n 的額外陣列——合併排序使用 O(n) 額外空間——而且它是穩定的（平局時優先取左段）。

// merge sorted a[lo..mid] and a[mid+1..hi] into a, using buffer tmp
void merge(int a[], int tmp[], int lo, int mid, int hi) {
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi)
        tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++]; // <= keeps it stable
    while (i <= mid) tmp[k++] = a[i++];   // leftovers, left run
    while (j <= hi)  tmp[k++] = a[j++];   // leftovers, right run
    for (int t = lo; t <= hi; t++) a[t] = tmp[t];
}

合併步驟：齊頭走過兩段有序序列，總是輸出較小的隊首。

快速排序：圍繞基準劃分

快速排序的拆分方式不同。選一個元素作基準（pivot），然後劃分：重排陣列，使比基準小的都在它左邊、比它大的都在它右邊。此時基準已落到最終位置；再對左右兩部分遞迴。無需合併——合併是免費的。

Partition [ 3  7  1  6  2 ] with pivot = 2 (last element):

  scan, swapping elements < pivot to the front:
  [ 1  3  7  6 | 2 ]   ( 1 < 2, moved left )
  place pivot after the small ones:
  [ 1 | 2 | 3  7  6 ]
        ^pivot now in final spot; recurse on [1] and [3 7 6]

劃分圍繞基準切開；基準落到它的最終位置。

// Lomuto partition: pivot = a[hi]; returns pivot's final index
int partition(int a[], int lo, int hi) {
    int pivot = a[hi], i = lo;
    for (int j = lo; j < hi; j++)
        if (a[j] < pivot) std::swap(a[i++], a[j]); // small ones to front
    std::swap(a[i], a[hi]);                         // pivot into place
    return i;
}
void quicksort(int a[], int lo, int hi) {
    if (lo >= hi) return;                  // base case
    int p = partition(a, lo, hi);
    quicksort(a, lo, p - 1);
    quicksort(a, p + 1, hi);
}

快速排序原地排序——只有遞迴堆疊是額外空間。

基準的選擇至關重要

如果基準能可靠地把陣列切在中點附近，快速排序平均為 O(n log n)——而它緊湊的內層迴圈讓它在實踐中很快。但一個糟糕的基準（比如總取最小值）每次只切下一個元素，造成 n 層嵌套，最壞為 O(n^2)。平衡時快速排序使用 O(log n) 堆疊空間。

Good pivot (near middle)        Bad pivot (always smallest)

   [........n........]            [........n........]
     /           \                pivot | [....n-1....]
  [n/2]        [n/2]                       pivot | [..n-2..]
  / \           / \                              pivot | [n-3]
 ...           ...                                    ...
 ~log n levels, O(n) each       n levels, O(n) each
   => O(n log n)                  => O(n^2)

均衡的拆分給出 O(n log n)；極度不均的拆分退化為 O(n^2)。

選哪個——以及 std::sort 做了什麼

需要保證 O(n log n) 且要穩定（如鏈結串列、外部/多鍵排序）？選合併排序。
排序記憶體中的陣列、想要原始速度且額外空間少？快速排序（配好基準）通常勝出。
在實踐中，直接呼叫 std::sort——它是 introsort：快速排序，但會回退到堆積排序以躲開 O(n^2)，並在極小子陣列上回退到插入排序。

#include <algorithm>
#include <vector>
std::vector<int> v = {5, 2, 8, 1};
std::sort(v.begin(), v.end());          // O(n log n), introsort
std::stable_sort(v.begin(), v.end());   // O(n log n), stable (merge-based)

優先用標準函式庫；當平局必須保持順序時改用 std::stable_sort。

這個道理比排序本身更寬廣：了解一個演算法如何達到它的複雜度——以及它在哪裡會失敗——能讓你挑對工具，並放心把其餘的交給函式庫。下一篇我們問更深的問題：O(n log n) 是排序所能達到的極限嗎？