对硬盘中的大量整数进行排序

给定硬盘上 100 GB 整数数据，RAM 为 2 GB，如何以最少的磁盘操作对整数进行排序。这里从磁盘获取一个数字被视为一次磁盘操作（尽管实际上可以获取一块数据）。

我们可以使用磁盘上的额外空间进行临时存储，而不需要考虑清理已使用的临时空间的操作。

正如其他人所指出的，您可以使用 O(n)计数排序。但是，您还需要考虑一些其他问题。我们假设您存储 32 位整数，即 100GB ~ 27e9 个整数。

如果所有整数都相同，那么它将出现约 27e9 次，这比 32 位 int 还要大。因此您的计数器必须是 64 位整数。

对于 2GB RAM，您一次只能在 RAM 中存储 ~125e6 个计数器。如果我们不能对整数的分布做出任何假设，我们要么必须：

• 单独增加 HD 上的计数器，或者
• 忽略我们遇到的所有不在我们当前存储在 RAM 中的计数器数组中的整数。

我认为后一种选择更好。由于我们需要约 4e9 个 64 位计数器并且只能存储 2GB，因此我们需要运行整个数组约 16 次。如果我们考虑遇到诸如 0,1

因此，我认为对于你的问题的具体大小（100GB），N路合并sort 会更好，因为这只需要读取整个数组 log_2(100) ~ 8 次。

然而，如果面试官立即将问题改为“10TB阵列，仍然是2GB RAM”，那么计数排序将轻松获胜。