第5章 Sorting Atomic Items：原子项排序

从外存多路归并与 Snow Plow 出发，推导排序和置换下界，再以三路、多路和双枢轴快排说明分布式范式与多磁盘冲突。

学习目标

能解释“5 Sorting Atomic Items”如何比较归并、分布式排序、下界与多磁盘 I/O 组织
能逐项核对The Merge-Based Sorting Paradigm、Lower Bounds、The Distribution-Based Sorting Paradigm、Sorting With Multi-Disks∞，不把平台页数或相邻章节主题冒充原版目录
能固定输入和参数，按“Sort(N) = Theta((N/B) log_(M/B)(N/B))”手算一个最小样例，并找到输出或成本的首个分叉
能注入“归并扇入超过可用缓冲页，模型声称的顺序 I/O 在实现中退化为抖动”，保存基线、故障、恢复和同输入重放证据

来源、版次与独立重写边界

“5 Sorting Atomic Items”对应 Paolo Ferragina 的 Pearls of Algorithm Engineering（Cambridge University Press，2023）。出版社书籍页确认作者、版次、ISBN、318页与算法工程定位；官方目录页和官方前置信息 PDF共同给出16章、61个编号节与索引的正式顺序。

对“5 Sorting Atomic Items”而言，当前公开可核验材料是出版社目录、前言与书籍说明，并非获授权完整正文。因此，下方中文讲解、公式推导、代码和实验是按公开目录坐标进行的独立教学重写，不声称逐段翻译原书；涉及“比较归并、分布式排序、下界与多磁盘 I/O 组织”的结论必须由本页的最小输入、预言机与成本记录重新证明。

官方目录坐标：5 Sorting Atomic Items

5.1 The Merge-Based Sorting Paradigm：在本页正文中以“比较归并、分布式排序、下界与多磁盘 I/O 组织”的对象、状态、复杂度或工程边界核对。
5.2 Lower Bounds：在本页正文中以“比较归并、分布式排序、下界与多磁盘 I/O 组织”的对象、状态、复杂度或工程边界核对。
5.3 The Distribution-Based Sorting Paradigm：在本页正文中以“比较归并、分布式排序、下界与多磁盘 I/O 组织”的对象、状态、复杂度或工程边界核对。
5.4 Sorting With Multi-Disks∞：在本页正文中以“比较归并、分布式排序、下界与多磁盘 I/O 组织”的对象、状态、复杂度或工程边界核对。

从“比较很快，搬动很慢”开始

sorting atomic items处理 n 个固定长度项目。字符串的比较成本依赖长度，将在第7章单独讨论；本章把每项视为一个不可拆分原子。

RAM 中比较排序需要 Theta(n log n) 次比较，给定目标排列的 permuting（置换）只需 Theta(n) 次移动。先预测当 n 远大于内部存储 M、磁盘每次传输 B 项时，两者差距是否仍然存在：一次 I/O 搬一整页，任意目标排列会把原本连续的项目打散，数据移动本身可能与发现排序顺序一样困难。

本页沿两条互补路线展开：merge-based sorting paradigm（基于归并的排序范式）先递归排好小段再融合；distribution-based sorting paradigm（基于分布的排序范式）先按枢轴分桶再递归。二者都要把二叉扇出扩到约 M/B，才能减少全量读写数据的层数。

二路归并先利用连续 I/O

合并两个总长 z 的有序段，只需两个输入页和一个输出页。每次较小项被输出后推进对应指针；跨页才读取下一块，输出页满才写回。因此在 M 至少容纳3B时，Merge 的 I/O 为 Theta(z/B)。

若机械套用二叉递归，每层读写全部 n 项，得到 Theta((n/B) log n)。但当子数组大小降到 M 时，可一次读入内部存储，之后所有内部比较不再产生外部 I/O。停止递归后，真正的外存层数是 log(n/M)：

T_{\mathrm{binary}}(n) = \Theta\left(\frac{n}{B} \log_2\frac{n}{M}\right)

工程阈值实际是 cM。原地 Heapsort 或 Quicksort 的 c 可接近1；内部 Mergesort 还需辅助数组，c 应明显小于1。渐进式里 c 是常数，真实系统中它会决定是否多做一次全量 pass。

Snow Plow 让初始有序段平均翻倍

通常每段最多 M 项。（雪犁）把 H 与冻结区 U 共同放进 M：

用 M 项建立最小堆 H，U 为空；
输出 H 的最小值 min，并读取下一项 next；
若 next 不小于 min，放回 H，仍可属于当前递增 run；
若 next 小于 min，放入 U，留给下一 run；
H 为空时当前 run 结束，U 恰好填满并成为下一阶段的堆。

SnowPlowPhase(H, input):
  U = empty
  while H is not empty:
    minimum = H.extract_min()
    output minimum
    next = input.read()
    if next exists:
      if next < minimum:
        U.append(next)
      else:
        H.insert(next)
  return U

输出最小值单调不减，所以 run 有序；初始 H 的 M 项都会输出，所以 run 至少长 M。在随机排列假设下，新读项目约一半进入 H、一半冻结进 U。阶段结束时 U 有 M 项，意味着约读取2M项，因此 run 平均长度约2M，可少一次归并 pass。

输入已逆序时，每个 next 都被冻结，run 只有 M；输入已升序时，H 可持续接纳新项，整个文件成为一个 run。2M 是分布假设下的平均，不是最坏保证。

数据压缩也可“虚拟增大 M”：有序整数 run 存差分，再用变长整数编码，能让更多项目驻留或让传输页承载更多项目。但压缩/解压 CPU、随机访问需求和异常大差分必须纳入实验。

多路归并把扇出提高到 M/B

二路 Merge 只用3个内存页，浪费其余空间。保留一个输出页后，可为 k 个输入 run 各缓存一页：

k = \left\lfloor\frac{M}{B}\right\rfloor-1

用含 k 个“当前项、来源 run”对的最小堆选下一输出。某 run 的缓存页耗尽时顺序读取下一页；总长 z 的 k 个 run 仍只需 Theta(z/B) I/O，CPU 每项做 O(log k) 堆操作。

KWayMerge(runs):
  reserve one input page per run and one output page
  heap = first item of every nonempty run
  while heap is not empty:
    (value, run) = heap.extract_min()
    output.append(value)
    refill output page when full
    if run has next item:
      heap.insert(run.next(), run)

初始约 n/M 个 run，每层减少 k 倍，于是的总 I/O 为：

\operatorname{Sort}(n) = \Theta\left( \frac{n}{B} \log_{M/B}\frac{n}{M} \right)

这就是单磁盘原子项排序的目标量级。Snow Plow 或压缩增大有效 M，会同时增大初始 run 并影响对数底数，价值可能跨越整次全量读写。

排序下界：一个 I/O 能产生多少新排列

在 RAM 中用比较决策树证明：n! 个可能顺序要求二叉树深度至少 log(n!)，即 Omega(n log n) 比较。

外存决策树把一个节点改为一次 I/O。读入 B 个新项目时，它们可与内部 M-B 个项目交错，并在新项目间产生排列；内部存储中的比较本身免费。对一次 I/O 的分支能力计数，再要求整棵树至少区分 n! 个排列，可得单磁盘比较排序下界：

\Omega\left( \frac{n}{B} \log_{M/B}\frac{n}{M} \right)

所以多路 Mergesort 在不可分原子、只移动不复制销毁、比较模型等假设下 I/O 最优。下界不是所有数据类型的绝对定律：定长整数可用基数性质，压缩记录改变有效 B，分布假设也可能允许其他算法。

置换的目标排列已给出。可以逐项随机搬动，花 O(n) I/O；也可创建“目标位置、源位置”对，按源排序后顺扫绑定真实项目，再按目标排序，花排序量级。因此：

\operatorname{Permute}(n) = \Theta\left( \min\left\{ n, \frac{n}{B}\log_{M/B}\frac{n}{M} \right\} \right)

在实际 B 通常远大于很小的对数层数时，min 中排序项更小，置换与排序具有相同 I/O 量级。结论是：瓶颈常在实现数据重排，而不是算出排序 permutation。

三路划分让重复键一次到位

经典 Quicksort 选一个 pivot，把数组分成小于与大于两部分。固定取首项会被有序输入打成 n-1 与0，退化到 Theta(n 的二次方)。

三路划分维护小于、等于、大于三段。扫描当前项时，用至多两次交换把它放入相应边界；等于 pivot 的整段已处最终值域，不再递归。重复键很多时，这比把等值项散到两边显著减少工作。

std::pair<std::size_t, std::size_t>
partition_three_way(
    std::vector<int>& values,
    std::size_t first,
    std::size_t last,
    int pivot) {
    std::size_t less = first;
    std::size_t current = first;
    std::size_t greater = last;
 
    while (current < greater) {
        if (values[current] < pivot) {
            std::swap(values[less++], values[current++]);
        } else if (values[current] > pivot) {
            std::swap(values[current], values[--greater]);
        } else {
            ++current;
        }
    }
    return {less, greater};
}

随机 pivot 让任何固定输入都无法稳定制造坏划分，期望比较不超过约 2n ln n。取 2s+1 个随机样本的中位数可提高平衡概率，但增加样本选择成本；随机选择算法可在平均 O(s) 内找样本中位数。

真正实现还要控制栈。每次只递归较小分区，对较大分区用 while 继续，即 tail recursion elimination（尾递归消除）。递归子问题至多减半，栈深最坏 O(log n)；小于几十项时切换 InsertionSort，减少调用开销。

多路分布是多路归并的对偶

Multi-way Quicksort 取 k-1 个枢轴，把一个输入流分到 k 个输出桶。内存布局与归并相反：一个输入页、k 个输出页。令 k 为 Theta(M/B)，每次分布读写全部 n 项，平衡时只需 log base k of (n/M) 层。

难点是 k 个枢轴。随机抽取 (a+1)k-1 个样本，内部排序后每隔 a+1 项取一个 pivot。取 a+1=12 ln k 时，本页用 Chernoff 与 union bound 证明：每桶少于 4n/k 的概率至少1/2；失败就重抽，期望常数轮。

ChoosePivots(S, k, a):
  sample (a + 1) * k - 1 positions uniformly
  sort sampled values in memory
  for i from 1 to k - 1:
    pivot[i] = sample[(a + 1) * i]
  return pivot

这样多路分布同样达到 Theta((n/B) log base M/B of (n/M)) I/O。实际系统还要处理倾斜、重复 pivot、桶缓冲回压和样本排序是否真的放入 M。

本页也讨论 dual-pivot Quicksort：两个 pivot p、q 把数组分成小于 p、位于二者之间、大于 q 三段。历史 Java 7 实现以约1.9n ln n比较换取约0.6n ln n交换，实测收益与分支预测、缓存和流水线有关。这说明渐进相同的算法仍需测量微架构成本。

多磁盘排序：带宽增加也带来冲突

sorting with multiple disks（多磁盘排序）让 D 个磁盘并行传输 DB 项。最简单的把设备视为 B'=DB 的大页，可直接复用单盘算法。

但对数底数从 M/B 降成 M/(DB)，没有充分利用磁盘独立性。真正的多磁盘下界为：

\Omega\left( \frac{n}{DB} \log_{M/B}\frac{n}{M} \right)

注意底数仍是 M/B，而不是 M/(DB)。要达到它，每次必须从不同磁盘各读写一页。

条带化保证顺扫单个 run 时可并行读 D 页，却不能保证多个输出桶同时满时，它们的下一块位于不同磁盘。若都指向 D2，本应一次完成的 D 块写入会串行成 D 次；多路归并读取多个 run 也有同类冲突。

GreedSort 的思路是让每个磁盘独立选择两个“最好块”：一个有当前最小 minimum，一个有当前最小 maximum；合并后输出较小块，把较大块写回对应 run。局部选择避免跨盘争抢，先生成 L-regressive 的近似有序序列，再用可线性 I/O 处理短序列的 ColumnSort 滑窗完成排序。

其细节复杂，但工程结论直接：增加磁盘数量只提高理论带宽，不自动提高算法吞吐。布局必须保证每轮请求能分散到 D 个独立设备，并监控热点、队列深度、写放大和尾延迟。

从模型到可复查外排实现

外排测试应同时检查顺序与资源。正确性可验证输出非递减、长度与输入相同，并对“值、原位置”排序后确认多重集合完全相等。稳定排序还要检查等键原相对顺序。

基准至少覆盖随机、有序、逆序、重复键、极度倾斜和接近 M 边界的数据；分别记录初始 run 长度分布、merge fan-in、pass 数、读写字节、压缩比、CPU、临时盘峰值和设备并行度。

Snow Plow 的2M、过采样的平衡概率、双枢轴的分支优势都依赖分布或硬件。理论上界决定不会怎样失控，实验决定目标数据上哪个常数真正主导。

先预测，再操作三个章专属实验

分步1 / 3

1. 成本模型与工作集

在“5 Sorting Atomic Items”中先预测层级和访问模式如何改变“Sort(N) = Theta((N/B) log_(M/B)(N/B))”，再切换工作集与局部性；最终结果相同不代表代价相同。

Cost-model laboratory

5 Sorting Atomic Items

比较归并、分布式排序、下界与多磁盘 I/O 组织

工作集所在层级

规模8192

传输256

相对成本8×

Sort(N) = Theta((N/B) log_(M/B)(N/B))

不变量：输出全序、元素多重集不变，且每轮归并的输入缓冲与输出缓冲不超 M

可重放工程合同

“5 Sorting Atomic Items”的实验必须保留：初始 runs、扇入、M/B、比较数、块读写、校验和与排序预言机。本章性能数据至少预热一次、重复多次并报告分布；正确性必须与独立预言机比较，不能只比较两个共享同一错误的优化实现。

练习与答案

练习

问题 1：正式目录。 “5 Sorting Atomic Items”的公开目录边界是什么，平台如何证明没有把其他章主题混入？

问题 2：最小反例。 怎样验证“Sort(N) = Theta((N/B) log_(M/B)(N/B))”不是只写在页面上的公式？

问题 3：恢复证据。 怎样证明“归并扇入超过可用缓冲页，模型声称的顺序 I/O 在实现中退化为抖动”已经修复？

本章回顾

原子项固定宽度，外存排序的主要成本是整页数据移动。
子数组放入 M 后停止递归，可把二路归并外存层数降到 log(n/M)。
Snow Plow 用 H 与 U 生成至少 M、随机输入平均约2M的初始 run。
多路归并以约 M/B 扇出达到 Theta((n/B) log base M/B of (n/M)) I/O。
排序下界与置换下界说明现实外存参数下，搬动数据已与排序同阶。
三路划分把等于 pivot 的项目一次移出递归，并需控制 pivot 与栈深。
多路 Quicksort 用一个输入页和 k 个输出页，是多路归并的对偶。
过采样以 Theta(k log k) 样本提高 k 个桶同时平衡的概率。
多磁盘条带化不自动最优；同盘冲突会让 D 路传输退化为串行。