利用空间训练器对数据进行排序

Question

现在的问题很简单。您有1000 MB，您必须对其进行排序。现在的问题是，您只有100 MB的空间来排序数据。(假设1000 MB存储在磁盘中，您只有100 MB的Ram来对数据进行排序。-在任何时候，您只能在Ram中拥有100 MB的数据。)

现在我想出了一个解决方案：

1. 将数据分成10部分--每部分100 MB，并使用快速排序对其进行排序。
2. 然后将所有的数据块写入硬盘中。
3. 现在从每个块中选择前10 MB，然后合并。现在您有100 MB。现在将这100 MB分开。
4. 现在做同样的事。从每个块中选择下一个10 MB并合并。
5. 继续这样做，然后连接数据。

现在我面临的问题是，当我们每次连在一起时，我们都要分别合并100 MB，我们就会犯错误。(这100 MB也应该合并在一起。)

我该如何解决这个问题？

Answer 1

外部合并排序与合并阶段的内部版本不同。在您的问题中，您正试图将内部合并算法直接应用于外部合并。

因此，您最终不得不合并两块大小为n / 2的块。正如您正确地注意到的，这将无法工作，因为您耗尽了内存。

让我们假设您有足够的内存来对所有元素中的1/k进行排序。这给您留下了k排序列表。不是合并两个列表，而是一次性合并所有k：

1. 选择输出缓冲区大小。一个好的价值似乎是n / 2。这使n / 2内存用于输入缓冲或每个子块的m = n / (2 x k)。
2. 从每个子块读取第一个m元素。现在，所有内存都被使用了，并且内存中每个子块的m元素都是最低的。
3. 从每个k输入缓冲区中选择最低值。将此值附加到输出缓冲区中。重复，直到一个输入缓冲区耗尽为止。
4. 如果其中一个输入缓冲区耗尽，请从磁盘上的子块读取下一个m元素。如果没有更多的元素，那么就完成了这个子块。
5. 如果输出缓冲区已满，则将其附加到输出文件并将其位置重置为开始。
6. 从(3)开始冲洗并重复，直到所有的子块都用完。

现在对输出文件进行排序。

您可以将输入缓冲区看作排序桶上的一组流缓冲区。检查流并从所有流中选择最佳(即最低)元素，并将其保存到输出列表中。从外部看，它是一个流合并，具有智能预取和输出缓冲。

Answer 2

您需要重复步骤3和4. N-1的次数。