浅谈外排序与非比较排序

1. 需求

在以下严格限制下设计一种排序算法，

1. 只能使用比较器接口，不能使用任何库函数；
2. 内存上限为 $O(\sqrt{n})$；
3. 允许运行时间为 $O(n^2)$。

要求：

1. 给出算法设计与伪代码；
2. 证明其正确性；
3. 分析其在极限情况下的行为；
4. 实现一个刻意低效但正确的版本，解释为何“慢”仍“合理”。

2. 初步思路

很容易想到将序列分块，每块分别快速排序，然后进行归并排序。假设块长为 $M$，分成 $K$ 个块。

首先块内进行快速排序，得到 $K$ 个有序块（run）。接下来开始归并。

假设内存最多同时打开 $W$ 个文件（含输入输出），则每次可以归并的路数为 $W-1$（留一个输出缓冲区）。

将 $K$ 个有序块分成若干组，每组包含 $R = W-1$ 个块（最后一组可能不足）。对每组做 $R$ 路归并，产生一个"大组"作为中间结果写回磁盘。组数 $G = \lceil K / R \rceil$，每个大组的大小约为 $R \times M$。

以此类推。如果 $G \leq R$，则直接将 $G$ 个大组做 $G$ 路归并，输出最终结果，结束。如果 $G > R$，则需要递归地进行多轮归并。每次将现有的中间文件分组，做多路归并，直到最终只剩 1 个输出文件。

根据这个似乎可以得出归并轮数是 $\log_W K$，但实际上并非如此。可能需要增加归并轮数来避免磁盘 IO 变成随机访问。

3. 实现

3.0 前置语法

site_t 是一种无符号整数类型，专门用来表示对象的大小和数组索引。其会根据平台自适应为 uint 和 ulong。

constexpr 代表编译期常量。

const 函数不会修改成员变量的值。constexpr 让函数变成可以在编译期间计算。

3.1 计时

C++ <chrono> 库中有两个时钟，真实时间 system_clock 和到目前为止的某个时间 steady_clock（但是这个起点没有意义）。而 high_resolution_clock 往往是两者中的一个。

1

auto start = std::chrono::system_clock::now();

如果直接 end - start，会得到一个底层 Tick 数，因此常用的做法是：

1
2
3
4
5
6
7
8
9

auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);

std::cout << ms.count() << " ms\n";

/*
duration_cast<std::chrono::seconds> s
duration_cast<std::chrono::microseconds> μs
duration_cast<std::chrono::nanoseconds> ns
*/

关于获取真实时间的方法（接下来那个闹钟项目肯定需要用到这个），我觉得在这个时代去学习这个没什么意义（直接 vibe 掉就行了），这里略去。

3.2 IO 设计

该算法的瓶颈往往不在排序而在于 IO。重点是千万不能一个一个读。

RAM 的读写速度是纳秒级，可以按字节直接访问。而硬盘是块设备，数据以固定大小的“扇区”（比如 512 B 或 4 KB）为单位组织，必须整块读写。而 HDD 需要寻道，会更慢。

不是很想学具体的 CPU、内存和磁盘的交互原理，至少不是在这篇文章中。

逻辑已经清楚，具体的实现交给 AI。

可能的技巧是预取 Prefetch：预测未来需要哪些数据，提前开始读，让计算和 IO 重叠。不在本文内考虑。

4. 非比较排序

记录一下没学过的基数排序：按照从低位到高位，进行稳定的计数排序。

在初期想过将值域分成若干块，然后每块进行计数排序之类的，但是值域块不好分，分错了还需要重分（因为我打算法竞赛时没学过桶排序，发现这就是桶排序）。实际上这个思路并非不可行，下面稍微讨论一下。

桶的值域划分可以考虑随机采样，但即使随机采样，在数据分布严重不均匀的时候也会炸缸。