c++ - 仅用 10 万个存储单元对 100 万个数字进行排序

Question

在 C++ 中，假设我们知道数字的范围，是否可以仅使用 100,000 个存储单元对 100 万个数字进行排序？

具体来说，一个.bin文件包含给定范围内的一百万个数字，需要将这些数字按降序排列到另一个.bin文件中，但我只允许使用大小为100,000的数组进行排序。有什么想法吗？

Answer 1

我想我在 SO 或 Quora 的某处读到了关于 map-reduce 的内容:

除以 100 万。数字分成 10 个 block 。读入第一个 100k 数字 block ，使用快速排序对其进行排序，然后将其写回原始文件。对其余 9 个 block 执行相同的步骤。然后对原始文件中的 10 个排序 block 执行 10 向合并(为此你只需要 10 个单元格)并将合并的输出写入另一个文件。您可以写入约 100k 的缓冲区，然后将其刷新到输出文件以加快写入速度。