我有一个500GB的文本文件，大约有10亿行，需要按照字母顺序sorting。 什么是最好的algorithm使用？ 我的实施和设置是否可以改进？
现在，我正在使用coreutils sort命令：
LANG=C sort -k2,2 --field-separator=',' --buffer-size=(80% RAM) --temporary-directory=/volatile BigFile 我在一个120GB RAM和16核虚拟机上运行AWS EC2。 它占用了大部分时间。
/ volatile是一个10TB的RAID0arrays。
“LANG = C”技巧提供了x2的速度增益（感谢1 ）
默认情况下，“sorting”使用可用RAM的50％。 上升到80-90％会有所改善。
我的理解是，gnu'sort'是O（n log n）合并sortingalgorithm的一个变种，它是最快的：参见2 ＆ 3 。 将移动到QuickSort帮助（我很高兴与不稳定的sorting）？
有一件事我注意到，只有8个内核被使用。 这与在linux coreutils sort.c中设置为8的default_max_threads有关（见4 ）。 这将有助于重新编译sort.c与16？
谢谢！
跟进 ：
@dariusz
我用克里斯和你的build议如下。
由于数据已经批量生成：我分别对每个桶进行分类（在几台独立的机器上），然后使用“sort –merge”function。 像魅力一样工作，速度要快得多：O（log N / K）vs O（log N）。
我也从头开始重新考虑这个项目：一些数据后处理现在在生成数据的时候执行，所以在分类之前可以丢弃一些不需要的数据（噪声）。
总而言之，数据量的减less和分类/合并导致了实现我的目标所需的大量计算资源的减less。
感谢您的所有有用的意见。
quicksort over mergesort的好处是没有额外的内存开销。 mergesort的好处是保证O（n log n）的运行时间，如果枢轴点采样很差，那么quicksort会更糟。 如果您没有理由担心内存使用，请不要更改。 如果你这样做，只要确保你选择一个快速排序实现，确保实质性的数据透视。
我不认为这将有助于重新编译sort.c. 这可能是微观优化规模。 但是这里的瓶颈将是内存/磁盘速度，而不是可用的处理器数量。 我的直觉是，8个线程已经将您的I / O吞吐量最大化，而且您不会看到性能改进，但是这肯定取决于您的具体设置。
而且，通过利用数据分布，可以显着提高性能。 例如，均匀分布的数据可以通过一个单独的桶排序过程非常快速地排序，然后使用mergesort对桶进行排序。 这也降低了mergesort的总内存开销。 如果mergesort的内存复杂度为O（N），并且可以将数据分成K个桶，则新的内存开销为O（N / K）。
只是一个想法：
我假设文件内容生成了相当长的一段时间。 编写一个应用程序（脚本？），它会周期性地将上一个生成的文件移动到另一个位置，将其内容附加到另一个文件，对该不同文件执行排序，然后重复，直到收集到所有数据。
这样你的系统会花费更多的时间排序， 但是结果会更快提供 ，因为排序部分排序的数据比排序未排序的数据要快。
我想，你需要分两步进行：
这是例子。
想象一下，你只有桶限制2行，你的输入文件是：
infile：0000 0001 0002 0003 5 53 52 7000
在第一次迭代，你读你的输入文件“超级桶，空前缀”，并根据第一个字母拆分。
将会有3个输出文件：
0：000 001 002 003
5 :(空）3 2
7：000
如您所见，带有文件名/前缀7的存储桶只包含一个记录000，即“7000”，拆分为7个文件名和000个尾部的字符串。 因为这只是一个记录，所以不需要再分割这个文件。 但是，文件“0”和“5”包含4个和3个记录，超过了限制2个。因此，需要再次分割它们。 拆分后：
00：01 02 03
5 :(空）
52 :(空）
53 :(空）
7：000
正如你所看到的，前缀“5”和“7”的文件已经被分割了。 所以，只需要分割文件“00”。
正如你所看到的，分裂之后，你将有一组相对小的文件。 此后，运行第二阶段：
排序文件名，并按照排序顺序处理文件名。 对每个文件进行排序，然后将resut添加到输出中，并将文件名添加到输出字符串中。