外部排序

Question

在这个网页中:

http://web.eecs.utk.edu/~huangj/CS302S04/notes/external-sorting2.html

将生成的运行合并为连续更大的运行,直到文件排序.

正如我引用的那样,我们如何将产生的运行合并在一起??? 我们没有那么多记忆.

Answer 1

想象一下,你有1到9的数字

9  7  2  6  3  4  8  5  1

让我们假设一次只有3个适合内存.

因此,您将它们分成3个块并对每个块进行排序,将每个结果存储在一个单独的文件中:

279
346
158

现在,您将打开三个文件中的每个文件作为流,并从每个文件中读取第一个值:

2 3 1

输出最低值1,并从该流中获取下一个值,现在您已经:

2 3 5

输出下一个最低值2,然后继续,直到输出整个排序列表.