我正在尝试解决如何高效地对一个无法在内存中容纳的大型数据集进行排序的问题。从高层次上看，显而易见的答案是使用一些标准算法对适合在内存中容纳的整块进行排序，将这些块写入磁盘，然后合并它们。 合并它们是问题所在。
假设数据分成C个块，因此我有C个文件要合并。如果我一次进行C路归并，则技术上我有一个O（N ^ 2）的算法，但只需要执行O（N）次向磁盘写入操作。如果我将它们迭代地合并为C / 2个文件，C / 4个文件等，则我有一个O（N log N）的算法，但必须执行O（N log N）次向磁盘写入操作，因此具有巨大的常数项。
这个难题的典型解决方案是什么？ 有没有好的解决方案？
简而言之，对于这个问题，并没有简单的答案。有许多答案，大部分都相当复杂-例如，Knuth第3卷就专门讨论了此问题。
通过查看已经完成的工作，一个显而易见的事情是，您真正想要尽量减少在初始排序期间创建的运行次数，并最大化每个运行的长度。为此，通常需要读取尽可能多的数据以适合内存，但不只是将其排序并写出，还需要将其放入堆中。然后，在写出每个记录时，读取另一条记录。
然后，您检查该记录是否应该在刚刚写出的记录之前或之后排序。如果应该在后面进行排序，则将其插入到堆中并继续。如果应该在前面排序，则将其插入到第二个堆中。
当第一个堆完全为空且第二个堆占用所有内存时，停止向当前运行添加记录。此时，重复此过程，将新运行写入新文件。
这通常会产生更长的中间运行阶段，因此合并它们的工作量要少得多。假设输入记录是随机排序的，则可以预计这将大致将每个运行的长度加倍-但是如果输入甚至部分排序，这可以利用现有排序来进一步延长运行长度。
顺便说一句，我当然没有发明这个过程-我可能是在Knuth中第一次读到它的，在“算法+数据结构=程序”（Niklaus Wirth）中也讨论了这个问题。 Knuth将该方法的首次发表归功于“H. Seward”，他在1954年在MIT的硕士论文中发表了此方法。如果您拥有Knuth的第二版，则可在第3卷的第254页找到它。我没有第三版的副本，因此无法提供页码。
我不到一个月前也听到过同样的问题，本地专家也给出了相同的回答。
“使用 unix sort 命令”
虽然我们最初认为这是对提问者的玩笑话，但事实证明这并不是。原因是那些聪明的人已经花了很多时间思考如何解决非常大的文件的问题，并提出了一种非常令人印象深刻的实现，可以充分利用现有资源。
因此，除非你打算重新发明轮子：即你有时间并且这是业务关键的问题，否则只需使用 unix sort 就可能是一个绝佳的主意。
唯一的缺点是它的晦涩语法。这个页面专门介绍该命令及其各种说明。
我的个人建议：取一小部分数据进行测试，确保命令确实能够完全满足你的要求。
外部排序是指一类可以处理大量数据的排序算法。当被排序的数据不能适应计算设备（通常是RAM）的主存储器，而必须驻留在较慢的外部存储器（通常是硬盘）中时，就需要使用外部排序。典型的外部排序算法使用一种排序-合并策略，该策略从排序小的子文件开始。基本算法由两个阶段组成：排序阶段和合并阶段。在排序阶段中，可以适应可用缓冲区空间的子文件被读入主存储器，使用内部排序算法进行排序，并作为临时排序子文件写回磁盘。在合并阶段中，排过序的子文件在一个或多个传递期间合并。
A-F开头的任何内容进行一次排序，然后再按照以G-M开头的字符串进行第二次排序，以此类推。然后将结果按顺序简单地追加即可。缺点是必须从磁盘读取数据C次。Nick 是正确的，使用外部排序。顺便说一下，你的 C-way 合并并不意味着 O(N^2)。对于合并，请使用优先队列，这样时间复杂度仍为 O(N log N)。
你也可以查看 缓存无关算法 进行排序。
为什么不使用http://www.amazon.com/Art-Computer-Programming-Sorting-Searching/dp/0201896850中的算法呢？
它们非常好，并且有详细的解释。
您是在就地排序还是创建新副本？如果您正在就地排序，则内存映射IO通常是一个很好的选择。只需映射整个文件，并对其执行归并排序。操作系统将保留文件的大部分内容在内存中，根据数据集，一般会最小化IO。
如果您编写自己的排序算法，一个技巧是在每次传递后反转您的方向。所以，如果在第一次传递中从始至终开始，那么在第二次传递时则从末尾到开头。如果将文件拆分为A、B、C和D四个部分，则在对C和D进行排序后，应合并C和D，而不返回A和B。原因当然是您的操作系统将部分文件页到内存中，您需要尽可能多地使用缓存。