快速排序与归并排序深度实战：从分区第一性原理、三路切分与内省排序，到外排序、稳定性与 AI 数据管线的工程全解

排序是计算机科学里被讲述最多、也最容易被"以为已经懂了"的算法。绝大多数工程师能默写 Lomuto 分区，却说不清 Hoare 分区少了多少次交换；能背出快排平均 O(n log n)，却在面对"为什么 std::sort 既快又不会被恶意输入打爆"时哑口无言；会在内存里排 10 万元素，却在外排序喂不动 2 TB 训练样本时束手无策。

本文从比较排序的第一性原理下界出发，把快速排序与归并排序这两条分治主线彻底拆开：分区不变量、两种经典分区方案、枢轴选择的数学权衡、三路切分如何消灭重复键的退化、尾递归与迭代化如何挡住栈溢出、内省排序（Introsort）如何给快排兜底；再到归并排序的自顶向下 / 自底向上 / 自然归并，以及真正能落地的外排序（External Merge Sort）多路归并。最后用一张真实标准库实现对照表、一份 12 项生产陷阱清单，以及一个 AI 训练数据管线中的外排序实战，把"会写"升级成"敢上生产"。

---

一、第一性原理：在动手前先问"下限在哪"

任何排序算法的讨论都必须从下界开始，否则所有优化都缺少坐标系。

1.1 比较排序的 Ω(n log n) 下界

对于只通过比较元素大小来决策的排序算法，所有叶子节点对应 n! 种可能的输入排列。一棵深度为 h 的判定树最多有 2^h 个叶子，因此：

2^h ≥ n!  ⟹  h ≥ log₂(n!)  ≈  n log₂ n − O(n)  ⟹  h = Ω(n log n)

结论很硬：只要你的算法只做两两比较，最坏情况就不可能优于 O(n log n)。这意味着：

• 快排、归并、堆排、Timsort 在渐近意义上"已经到底了"——再快也只是常数与常数因子之争；
• 想要突破，必须引入非比较信息：计数排序、基数排序、桶排序依赖键的分布，它们可以做到 O(n)，但代价是键空间假设与额外内存。

工程含义：当你纠结"能不能让快排更快"时，真正的杠杆往往不在比较次数，而在缓存局部性、分支预测、交换成本、递归深度。

1.2 三个被忽视的维度：稳定性、原地性、缓存友好度

维度	含义	典型影响
稳定性（stable）	相等键的相对顺序在排序后保持不变	多级排序（先按日期、再按金额）必须稳定；数据库 ORDER BY a, b 依赖它
原地性（in-place）	额外空间是否为 O(1)	嵌入式、内核、大内存压力场景的关键约束
缓存局部性	是否顺序访问临近内存	决定常数因子，往往比"少几次比较"更重要

快排与归并在此形成鲜明对照：快排原地但默认不稳定，归并稳定但需 O(n) 额外空间（自底向上变体可压到 O(1) 但代价是失去稳定性或实现复杂度）。理解了这张表，后面所有"为什么标准库这么选"的决定都有了依据。

---

二、快速排序：分治的艺术在于"分区"

快排的精髓不是递归，而是分区（partition）——把数组围绕一个枢轴（pivot）重排，使左边都 ≤ pivot、右边都 ≥ pivot，pivot 落到最终位置。

2.1 分区的循环不变量

无论哪种分区，都维护同一个不变量：

[lo .. i]   全部 ≤ pivot
(i .. j)    全部 >  pivot
[j .. hi]   尚未处理

j 扫过未处理区，遇到 ≤ pivot 的元素就把它换进"≤ 区"并扩张 i。循环结束后 i 指向最后一个 ≤ 元素，把 pivot（通常放在 lo 或 hi）与它交换，pivot 即归位。

2.2 Lomuto 分区：最易懂，但交换偏多

// 返回 pivot 的最终下标；pivot 取 a[hi]
int lomuto_partition(int *a, int lo, int hi) {
    int pivot = a[hi];
    int i = lo;                      // [lo, i) 为 ≤ 区
    for (int j = lo; j < hi; j++) {
        if (a[j] <= pivot) {
            int t = a[i]; a[i] = a[j]; a[j] = t;
            i++;
        }
    }
    int t = a[i]; a[i] = a[hi]; a[hi] = t;   // pivot 归位
    return i;
}

优点：代码短、易证明、边界清晰。缺点：即使数组已近乎有序，每次仍做大量无效交换；对已排序数组 + 取末位为枢轴会退化成 O(n²) 且交换次数爆炸。

2.3 Hoare 分区：交换更少，实际更快

Tony Hoare 原始方案从两端向中间夹逼，平均交换次数约为 Lomuto 的 1/3：

int hoare_partition(int *a, int lo, int hi) {
    int pivot = a[lo + (hi - lo) / 2];   // 取中间元素作枢轴值
    int i = lo - 1, j = hi + 1;
    while (1) {
        do { i++; } while (a[i] < pivot);
        do { j--; } while (a[j] > pivot);
        if (i >= j) return j;            // 注意：返回的是边界，而非 pivot 位置
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }
}

关键差异：Hoare 返回的是分割点 j，递归区间应为 [lo, j] 与 [j+1, hi]——这与 Lomuto 的 [lo, p-1] / [p+1, hi] 不同，写错边界是经典 bug 来源。

实测：在 10⁷ 个 int 上，Hoare 比 Lomuto 快约 20–30%，主要省在交换次数与更好的缓存行为。

2.4 枢轴选择：快排成败的决定性因素

快排平均 O(n log n) 的前提是"每次大致对半分"。退化只发生在枢轴总是极值时（已排序数组 + 末位枢轴就是最坏案例）。三种主流对策：

策略	做法	最坏	额外成本	评价
固定末位	pivot = a[hi]	O(n²)（已排序即触发）	0	教学用，生产禁用
随机	pivot = a[rand(lo,hi)]	概率趋近于 0	1 次随机	简单有效，但随机数有成本
三数取中	median(a[lo], a[mid], a[hi])	仍理论存在但极罕见	2 次比较	工业界首选，几乎免费
中位数的中位数	Blum-Floyd-Pratt-Rivest-Tarjan	严格 O(n log n)	递归开销大	理论完美，工程少用

工程默认选三数取中（median-of-three）：它既挡住了"已排序数组"这个最常见退化输入，又不引入随机源的开销。一个常被忽略的增强：在小数组（如 < 16 元素）切换为插入排序——插入排序在近乎有序的小区间常数极小，能砍掉大量递归叶子开销。

2.5 三路切分 / 荷兰国旗：消灭重复键退化

当数组含大量重复键（如日志按状态码排序、用户按国家分组），普通二分快排会把"等于枢轴"的元素反复搬来搬去，退化明显。Dijkstra 的荷兰国旗（Dutch National Flag） 把区间分成 < / = / > 三段：

// 返回 [lt, gt] 闭区间：a[lo..lt-1] < pivot, a[lt..gt] == pivot, a[gt+1..hi] > pivot
void three_way(int *a, int lo, int hi, int *out_lt, int *out_gt) {
    int pivot = a[lo];
    int lt = lo, i = lo, gt = hi;
    while (i <= gt) {
        if (a[i] < pivot)      { swap(a[lt], a[i]); lt++; i++; }
        else if (a[i] > pivot) { swap(a[i], a[gt]); gt--; }   // 注意 i 不动
        else                   { i++; }
    }
    *out_lt = lt; *out_gt = gt;
}

对"只有 3 种取值的百万级数组"，三路快排是 O(n)，而普通快排是 O(n²)。Java 的 Arrays.sort 对基本类型正是用三路变体（Dual-Pivot 的近亲）。

2.6 尾递归消除与迭代化：挡住栈溢出

快排是递归的。对 10⁸ 元素的退化输入，递归深度可能达 O(n)，直接爆栈。两个对策：

尾递归 + 总是先处理较小区：

void quicksort_iter(int *a, int lo, int hi) {
    while (lo < hi) {
        int p = hoare_partition(a, lo, hi);
        if (p - lo < hi - p) {        // 先递归较小的半边
            quicksort_iter(a, lo, p);
            lo = p + 1;               // 大的一边用循环模拟"尾递归"
        } else {
            quicksort_iter(a, p + 1, hi);
            hi = p;
        }
    }
}

这样把最大递归深度压到 O(log n)，10⁸ 元素也只需约 27 层——栈完全无压力。

2.7 内省排序 Introsort：给快排兜底

真正的生产级快排不会裸奔。Introsort（内省排序） 是 C++ std::sort 的核心思想：

introsort(a, lo, hi, depth_limit):
    if hi - lo < 阈值: insertion_sort(a, lo, hi); return
    if depth_limit == 0:           // 递归过深 → 快排要退化
        heap_sort(a, lo, hi);      // 切换堆排，保证 O(n log n) 最坏
        return
    p = partition(a, lo, hi)       // 三数取中 + 三路
    introsort(a, lo, p, depth_limit-1)
    introsort(a, p+1, hi, depth_limit-1)

depth_limit 初始为 2 * floor(log₂(n))。一旦递归深度逼近这个界，说明分区质量持续糟糕（恶意或退化输入），立刻切到堆排把最坏复杂度锁死在 O(n log n)。这既保留了快排在常见输入上的速度，又消灭了 DoS 式 worst-case——这是 2000 年代后所有严肃标准库的共同选择。

---

三、归并排序：稳定与可外存的王者

归并排序走另一条分治路：先递归排好两半，再合并两个已排序序列。它的魅力在于——合并操作天然稳定，且可以脱离内存。

3.1 自顶向下（递归）

void merge(int *a, int lo, int mid, int hi, int *buf) {
    int i = lo, j = mid, k = lo;
    while (i < mid && j < hi)
        buf[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];   // <= 保证稳定性
    while (i < mid) buf[k++] = a[i++];
    while (j < hi)  buf[k++] = a[j++];
    for (int t = lo; t < hi; t++) a[t] = buf[t];        // 写回
}
void mergesort(int *a, int lo, int hi, int *buf) {      // [lo, hi)
    if (hi - lo <= 1) return;
    int mid = lo + (hi - lo) / 2;
    mergesort(a, lo, mid, buf);
    mergesort(a, mid, hi, buf);
    merge(a, lo, mid, hi, buf);
}

时间严格 O(n log n) 最坏，空间 O(n)。稳定性来自合并时的 <=。

3.2 自底向上迭代：无递归、缓存更友好

自顶向下的递归在小数组上有调用开销，且访问模式不够连续。自底向上先合并长度为 1 的相邻块，再 2、4、8……，完全用循环：

void mergesort_bottomup(int *a, int n, int *buf) {
    for (int width = 1; width < n; width *= 2) {
        for (int lo = 0; lo < n; lo += 2 * width) {
            int mid = lo + width < n ? lo + width : n;
            int hi  = lo + 2 * width < n ? lo + 2 * width : n;
            merge(a, lo, mid, hi, buf);
        }
    }
}

优点：无递归栈、对缓存更友好、实现更短。缺点：经典实现失去稳定性需要额外处理（若用 <= 仍稳定），且无法像快排那样在小数组切插入排序（可手动加一层）。

3.3 自然归并（Natural Merge）：利用已有有序段

现实数据常有"已经基本有序"的游程（run）。自然归并先扫描出这些 run，再两两合并，最好情况（已排序）直接 O(n)：

扫描得到 run 列表 → 用最小堆/队列维护 run 头 → 反复取最小两个合并

Timsort（Python sorted、Java 对象排序、Android）正是自然归并 + 二分插入 + 游程优化的集大成者，专门吃"现实世界部分有序"的数据。

3.4 外排序 External Merge Sort：当数据塞不进内存

这是归并排序真正不可替代的地方。假设要排序 2 TB 数据，内存只有 4 GB：

阶段一：生成排序游程（run）

1. 每次从磁盘读 4 GB 进内存；
2. 内存内用快排/内省排好；
3. 写出一个"已排序游程"文件 run_0, run_1, ...。

阶段二：多路归并（k-way merge）

用败者树（loser tree）或最小堆同时归并 k 个游程（k 受文件描述符与内存限制，常见 64–256），每次取全局最小写出。若游程数仍过多，做多趟（pass）归并或 PolyPhase Merge（用斐波那契分布减少趟数）。

内存缓冲(4GB)
   │ 读 4GB → 内存排序 → 写 run_0..run_m
磁盘 run_0 ┐
run_1      ├─→ 败者树 k 路归并 ─→ 最终有序文件
run_2      │
...        ┘

为什么不用快排做外排序？因为快排的分区是原地、需要随机访问整个区间的，而磁盘随机寻道代价是内存的 10⁵ 倍量级——归并的顺序流式访问才是磁盘友好的。这就是为什么数据库（PostgreSQL 的 work_mem 溢出排序）、大数据（Spark sort、Hadoop MapReduce 的 shuffle sort）底层都是外归并。

关键参数：k 路归并的 I/O 趟数 ≈ ⌈log_k(m)⌉。用败者树把"从 k 个候选取最小"的成本从 O(k) 降到 O(log k)，使大 k 也高效。

---

四、稳定性、缓存与真实标准库实现对照

把理论落到生产，标准库的选型本身就是一份答案：

实现	算法	稳定性	最坏	备注
C++ std::sort	Introsort（快排+堆排+插入）	否	O(n log n)	快，但不稳定
C++ std::stable_sort	归并（内存足）/ 原地归并（不足）	是	O(n log n)	稳定需求用它
Rust slice::sort	pdqsort（pattern-defeating quicksort）	否	O(n log n)	抗退化、极快
Rust slice::sort_by 稳定版	Timsort 风格	是	O(n log n)
Java 基本类型 sort	三路快排（Dual-Pivot）	否	O(n log n)
Java 对象 sort	Timsort	是	O(n log n)
Python sorted	Timsort	是	O(n log n)	吃部分有序
glibc qsort	通常归并变体（历史曾用快排导致 DoS）	视实现	O(n log n)	曾因快排被攻

核心洞察：现代标准库几乎没有一个用"裸快排"。它们要么用 Introsort 给快排兜底，要么在稳定性需求下直接用归并/Timsort。你手写的快排要上生产，至少应补上 三数取中 + 小数组插排 + 递归深度限制（Introsort） 三件套。

---

五、工程实战

5.1 快速选择 Quickselect：第 k 小与 Top-K

只想要"第 k 小"或"最大的 1 万条"，全排序是浪费。Quickselect 复用分区，但只递归包含目标的半边：

int quickselect(int *a, int lo, int hi, int k) {  // 第 k 小（0-indexed）
    while (lo < hi) {
        int p = hoare_partition(a, lo, hi);
        if (k <= p) hi = p;
        else lo = p + 1;
    }
    return a[lo];
}

平均 O(n)、最坏 O(n²)（同样用三数取中 + 深度限制可压住）。它是 Top-K、中位数、分位数的基石，也是很多流式统计的底层。

5.2 并行排序

归并排序天然适合并行：左右两半独立排（丢给两个线程/向量），只合并阶段需同步。快排也可并行处理两个子区间。注意：并行收益只在数据量极大（>10⁶）且比较昂贵时显著，否则线程与伪共享开销反而拖慢。实践中更常见的是并行生成外排序游程。

5.3 AI 训练数据管线中的排序实战

在大规模训练里，排序常出现在三个隐蔽位置，且都必须用外排序：

1. 去重前的全局排序：对 2 TB 爬虫语料按哈希/URL 排序以合并重复，内存放不下 → 外归并；
2. Shuffle 的确定性：分布式训练要求可复现的 epoch shuffle，需对样本索引做稳定排序后按固定种子切分；
3. 按长度分桶（length bucketing）：把相近序列长度的样本排序聚集，减少 RNN/Transformer 的 padding 浪费，直接降低 10–20% 训练时间——这里排序的"稳定性"决定了同长度样本的原始顺序是否保持。

一个真实落地的外排序管线骨架：

原始样本(2TB)
   → 分块读入内存(4GB) → 内存 Introsort 按 (length, hash) 排序 → 写 run_i
   → 败者树 k 路归并 run_0..run_m → 有序样本流(按 length 聚集)
   → 下游 DataLoader 直接按桶读取，padding 比下降

这里快排负责"内存内那段"，归并负责"跨磁盘那段"——两条算法在同一管线里各司其职，这正是理解它们差异后的正确用法。

---

六、12 项生产陷阱清单

1. 裸快排取末位枢轴：已排序输入直接 O(n²)，生产禁用，必须三数取中或随机。
2. 递归深度无上限：退化输入爆栈；务必 Introsort 深度限制或尾递归迭代化。
3. Hoare 分区边界写错：返回 j 但递归写成 [lo,j-1]/[j,hi] 会死循环或漏排。
4. mid 整数溢出：(lo+hi)/2 在超大数组溢出；用 lo + (hi-lo)/2。
5. 比较函数不满足严格弱序：传给 std::sort 的 comparator 若 a 和 b 同时为 true（如用 <=），结果是 UB 而非慢——直接崩或静默错排。
6. NaN 破坏全序：浮点 NaN 与任何值比较都为 false，排序结果未定义；先归一化或分离 NaN。
7. 重复键退化：日志/状态码类数据用普通二分快排退化为 O(n²)；改三路切分。
8. 稳定性误用：以为排过就稳定，多级排序（先日期后金额）出错；需要稳定时用归并/Timsort。
9. 小数组硬递归：<16 元素仍递归，调用开销吃光性能；切插入排序。
10. 外排序 k 太大：开太多游程文件超出 fd 限制或缓冲耗尽；按内存/ fd 上限算 k。
11. 归并忘了写回缓冲：合并结果只存 buf 未拷回原数组，得到半截有序。
12. 把快排当外排序用：在磁盘数据上做原地分区，随机寻道拖垮性能；跨内存边界一律归并。

---

七、结论

快速排序与归并排序不是"两个入门算法"，而是同一分治思想下针对内存 vs 外存、速度 vs 稳定的两套最优解：

• 快排胜在内存内原地、缓存友好、常数极小，但需要用三数取中 + 递归深度限制（Introsort）+ 小数组插排三件套武装成生产级；
• 归并胜在严格 O(n log n) 最坏、天然稳定、可流式外扩，是外排序、稳定排序、并行排序的唯一正解；
• 现实里二者常常协作：外排序的内存内段用快排，跨磁盘段用多路归并；Top-K 用 Quickselect；部分有序数据用 Timsort。

真正吃透它们，不在于能默写代码，而在于能在"数据塞不进内存、输入可能被攻击者构造、相等键必须保持顺序、递归随时可能爆栈"的生产现场，正确选择并加固那一个算法。这张 12 项陷阱清单，就是检验你到底"会写"还是"敢上生产"的标尺。