我从一个讨论外部合并排序的链接中得到这个。
从幻灯片 6 示例：使用 5 个缓冲页面，对 108 个页面文件进行排序
Pass0：[108/5] = 22 次排序运行，每次运行 5 页（最后一次运行只有 3 页）
Pass1 [22/4] = 6 次排序运行，每次运行 20 页（最后运行只有 8 页）
Pass2：[6/3] = 2 次排序运行，80 页和 28 页
Pass 3：[2/2] = 1 个 108 页的已排序文件
问题：我的理解是外部合并排序，在 pass 0 中创建块，然后对每个块进行排序。在剩余的通行证中，您不断合并它们。因此，将其应用于上面的示例，因为我们只有 5 个缓冲页面，在 Pass 0 中，我们需要 22 个排序运行，每个运行 5 个页面。
现在，为什么我们要对剩余的通行证进行排序运行或合并？
当我们只有 5 个缓冲页时，它为什么会告诉第 1、6 次排序运行，每次运行 20 页？
合并到底发生在哪里？以及如何在每次通过时 N 减少，即从 108 到 22 到 6 到 2 ？
当您无法将所有数据存储到内存中时，外部合并排序是必要的。您可以做的最好的事情是将数据分解为排序的运行，然后在后续传递中合并运行。运行的长度与可用的缓冲区大小相关。
Pass0：您正在原地执行操作。因此，您将 5 页数据加载到缓冲区中，然后使用就地排序算法对其进行就地排序。这 5 个页面将作为一个运行存储在一起。
以下通行证：由于您正在合并许多页面的运行，因此您无法再执行操作。4 个页面被加载到缓冲区中，第 5 个是写缓冲区。合并与合并排序算法相同，但您将分治系数 B-1 而不是 2。当写缓冲区被填满时，它被写入磁盘并开始下一页。
复杂性：在分析外部归并排序的复杂性时，要考虑 I/O 的数量。在每次传递中，您必须读取一页并写入该页。设 N 为页数。每次运行将花费 2N。读一页，写一页。
让 B 是您可以保存缓冲区空间的页数， N 是页数。
将有 ceil(log_B-1(ceil(N/B))) 通行证。每个通道将有 2N 个 I/O。所以 O(nlogn)。
在每遍中，运行的页面长度增加 B-1 倍，排序运行的数量减少 B-1 倍。
Pass0：ceil(108 / 5) = 22，每次运行 5 页
Pass1：ceil(22 / 4) = 6，每次运行 20 页
Pass2：ceil(6 / 4 ) = 2，每次运行 80 页
Pass3：ceil(2 / 4 ) = 1 - 完成，108 页的 1 次运行
A. 由于它从未提到合并，我假设（希望）后来的“排序”通道正在合并。
B. 同样，假设这是合并，您需要一个缓冲区来保存合并的记录，并为每个要合并的文件使用剩余的缓冲区之一：因此，4 个输入文件，每个 5 页：20 页。
C. 认为我已经回答了现在合并两次的地方:)