外部内存合并排序

Question

谁能指出我对外部内存Mergesort的良好参考？我已经阅读了Wiki页面，但是很难完全理解它。动画可能会有所帮助，但我似乎找不到一个动画。

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

Answer 1

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