如何对不同文件中的多个 GB 数据进行排序？

Question

我有 50 个大约 10 GB 数字的文本文件。我必须对这些数字进行排序。我的第一个想法是使用应用合并排序，即分别对每个文件进行排序并合并它们。我正在使用数组来加载这些数字。当我 运行 应用程序时，我的程序由于内存不足而崩溃。所以我的问题是：

1. 使用哪种数据结构？
2. 如何管理内存？
3. 合并排序是正确的方法吗？如果不行请指教。

我们将不胜感激。

Answer 1

如果数字最多只有 7 位并且是整数，那么您可以使用 Counting Sort。

您只需要大约 40Mb 的内存，即可存储 1000 万个 4 字节整数，计算 0-9,999,999 中每个数字的个数。如果您必须处理超过 21.4 亿个重复的相同数字的可能性，那么您可以使用 64 位整数。将数组初始化为零，然后一次读取一个数字，更新每个数字的计数。完成后，您可以根据计数生成排序列表。