外部存储器合并排序

Question

任何人都可以指出我对外部存储器Mergesort的一个很好的参考吗？我已阅读维基页面，但无法准确理解它。动画可能有帮助，但我似乎无法找到一个。

基本上，我知道你在磁盘上有一定数量的块，并且你可以在内存中容纳一定数量的块。假设你有32块磁盘和4块内存。在第一遍中，您一次将4个块读入内存，将它们排序在内存中，然后将它们写回磁盘。所以在这一点上，你有8块分4块运行。合并工作如何？由于我在内存中有4块（假设我还有一块用于输出），我认为我应该能够一次合并这8个运行中的4个，然后合并接下来的4个运行。然后在最后一遍我想合并整个事情。但是，你不必每次都从磁盘读取每个块吗？那么这怎么不会成为n^2解决方案呢？

Answer 1

我想我现在明白了。当你合并时，你仍然必须读取磁盘上的所有块（让我们称之为B），但是你不必阅读它们B次。你只能读它们B日志B次。