algorithm - 外部合并排序的时间复杂度/成本

Question

我从 link 得到这个其中谈到了外部归并排序。

来自幻灯片 6 示例:使用 5 个缓冲页，对 108 页文件进行排序

• 第 0 次:[108/5] = 22 次排序运行，每次运行 5 页(最后一次运行只有 3 页)

• 第 1 轮 [22/4] = 6 次排序运行，每次运行 20 页(最后运行仅 8 页)

• 第 2 轮:[6/3] = 2 次排序运行，80 页和 28 页

• 第 3 轮:[2/2] = 1 个 108 页的排序文件

问题:我的理解是在外部合并排序中，在 pass 0 中创建 block ，然后对每个 block 进行排序。在剩余的通行证中，您不断合并它们。因此，将其应用于上面的示例，因为我们只有 5 个缓冲页，所以在 Pass 0 中很明显我们需要 22 次排序运行，每次运行 5 页。

1. 现在，为什么我们要对剩余的传递进行排序运行而不是合并？

2. 当我们只有 5 个缓冲页时，它如何告诉第 1 遍 6 次排序运行，每次运行 20 页？

3. 合并到底发生在什么地方？以及每次通过时 N 如何减少，即从 108 到 22 到 6 到 2？

Answer 1

当无法将所有数据存储到内存中时，外部合并排序是必要的。您可以做的最好的事情是将数据分解为排序的运行并在后续传递中合并运行。运行时长与可用缓冲区大小有关。

Pass0:您正在原地进行操作。因此，您将 5 页数据加载到缓冲区中，然后使用就地排序算法对其进行就地排序。这 5 页将存储在一起作为一个运行。

后续通行证:您无法再进行原地操作，因为您正在合并多个页面的运行。 4 页被加载到缓冲区中，第 5 页是写缓冲区。合并与归并排序算法相同，但您将分治 B-1 而不是 2。当写缓冲区填满时，它被写入磁盘并开始下一页。

复杂性:在分析外部归并排序的复杂性时，I/O 的数量是正在考虑的。在每一遍中，您必须读取一页并写入该页。令 N 为页数。每次运行将花费 2N。读一页，写一页。
令 B 为您可以容纳缓冲区空间的页数，N 为页数。
将有 ceil(log_B-1(ceil(N/B))) 遍。每个 channel 将有 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