外部归并排序第一趟为何无需设置输出页？

Great question—this is one of those subtle, easy-to-miss details in external sorting that confuses a lot of folks when they first dive into it. Let’s break down the key differences between the first pass and subsequent passes to clear this up:

核心区别：第一趟是「单块内部排序」，后续是「多段归并」 #

第一趟的操作逻辑 #

第一趟的核心是把磁盘上的无序数据切分成多个内存可容纳的有序段（也叫runs），流程是：

• 一次性读取B个页面到内存（全部内存缓冲都用来存放待排序的数据，没有预留）
• 用内部排序算法（比如快速排序、堆排序）把这B页的数据排好序
• 把排序完成的整个有序段直接写入磁盘

这里的关键是：我们是先完成排序，再一次性输出整个块——不需要在排序过程中同时处理输入和输出。内存里的排序结果本身就可以作为输出的数据源，不需要额外预留一个缓冲页来临时存储输出内容。写完当前这个有序段后，再读取下一批B页重复操作即可。

后续趟次的操作逻辑 #

从第二趟开始，我们进入多段归并阶段（比如k路归并），这时候的流程是流水线式的：

• 需要k个输入缓冲页（每个缓冲页对应一个有序段的当前读取页）
• 同时需要1个输出缓冲页：用来临时存储归并后的结果，当输出缓冲页写满时，批量写入磁盘；同时，输入缓冲页可以继续读取下一页，归并计算也持续进行

这里必须预留输出缓冲的原因是：我们要并行化「读输入、归并计算、写输出」三个操作，避免磁盘IO的等待时间拖慢整体效率。如果不预留输出缓冲，每次归并出一部分结果就直接写盘，会频繁中断归并计算，导致性能大幅下降。

举个直观的例子 #

假设可用缓冲页面数B=4：

• 第一趟：把4页读进内存，排序后直接写出4页的有序段——全程内存都用来存数据，没有额外缓冲的需求。
• 第二趟（2路归并）：需要2个输入缓冲页（分别读两个有序段的页），1个输出缓冲页（存归并结果），剩下1页可以作为替换缓冲（优化IO）——这时候必须预留输出页来维持流水线的连续运行。

简单来说：第一趟是「单块处理，先排后写」，后续是「多流归并，边读边排边写」，这就是为什么第一趟不需要预留输出缓冲的核心原因。

内容的提问来源于stack exchange，提问作者Zachary HUANG