外部排序（进阶）
复习
- 归并排序：分治与合并
- 存储层次：内存快、磁盘慢
- 文件：数据可以长期存放在磁盘上
本章为进阶内容，零基础读者可以跳过，不影响后续阅读。
TL;DR
- 数据大到放不进内存时，就需要外部排序
- 核心思路：先分块排序，再多路归并
- 减少磁盘读写，是外部排序的首要目标
- 多路归并能减少归并的轮数
正文
前面的排序都默认数据能全部放进内存。可如果数据有几百 GB，内存根本装不下，怎么办？这类“放不进内存”的排序，叫外部排序（external sorting）。
瓶颈不在 CPU，而在磁盘
内存和磁盘的速度差着好几个数量级。一旦数据要反复在磁盘上读写，磁盘 I/O 就成了绝对的瓶颈，CPU 算得再快也没用。
所以外部排序的第一原则是：尽量少读写磁盘。 这和我们前面讲的存储层次一脉相承——能少跑几趟慢速设备，整体就快得多。
先分块排序，再归并
外部排序的经典做法，正好建立在归并排序之上：
- 分块：把大文件切成许多小块，每块单独读进内存，用普通排序排好，再写回磁盘。这样得到许多有序的小段
- 归并：把这些有序小段，逐步合并成一个完整的有序文件
你看，这就是归并排序的“分治+合并”思路，只不过被搬到了磁盘上：分块排好，再合并。
多路归并，减少往返
合并时，如果每次只两两合并，那要把很多小段合并成一个大文件，就得来回读写好几轮，代价很大。
更好的办法是多路归并：一次同时合并几十甚至上百个小段。这样归并的“轮数”大大减少，磁盘读写的总趟数也随之下降。
“一次合并几路”，又受限于内存能同时容纳多少输入缓冲。于是，如何在“内存大小”和“归并路数”之间取平衡，成了外部排序的重要调优点。
又一次呼应主线
外部排序其实并不需要发明新的排序算法。它只是把归并排序的思想，放到“内存装不下、磁盘又很慢”的约束下重新施展。
这再一次印证：理解约束，比记住算法更重要。 同样是排序，数据能装进内存和装不进内存，就是两套不同的工程思路。
思考题 1
外部排序为什么把“减少磁盘读写”放在第一位？
思考题 2
外部排序为什么普遍采用“先分块排序、再多路归并”的策略？
小结
知识点
- 外部排序处理放不进内存的大数据
- 磁盘 I/O 是主要瓶颈
- 先分块排序得到有序小段
- 再多路归并，减少磁盘往返轮数
参考资料
- Wikipedia(zh)：外部排序：处理超出内存容量的排序
- Wikipedia(zh)：归并排序：外部排序的理论基础
思考题答案（仅供参考）
思考题 1
因为磁盘比内存慢好几个数量级，一旦数据要反复在磁盘读写，I/O 就成为压倒性的瓶颈，CPU 再快也没用。所以尽量减少磁盘读写，才最直接影响整体性能。
思考题 2
因为内存装不下全部数据，只能一块块读进来排序，得到若干有序小段；再用归并把这些小段合起来。多路归并还能一次合并多段，减少归并轮数和磁盘往返，因此成为经典策略。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪