为O整数的外部排序（N日志N）的读取和O（N）写道：

Question

我感兴趣的算法，我应该使用O(N log N)读取，满足int对外排序的要求和O(N)写

Answer 1

如果该类型排序（其中数据不能全部放入到核心在一次）的算法后的时候，我的解决方案来自于“革命”，当高端机器具有非常初期内存比大多数现代计算器少。我还没有制定出大O属性，但我认为这将是O（n）读取，O（n日志n）排序阶段（取决于所选的排序方法）和O（n）写入。

比方说，你的数据集有一个百万个元素，你只可以在内存中同时满足10万人。以下是我要做的：

• 在第一个100,000中读取，对它们进行排序并将其重新写入排序列表。
• 为每组100,000个做这个。
• 对10个组运行合并操作。

换句话说，一旦你的10个组在组内排序，从每个组抓取第一个条目。

然后写该最低那些10的（这是最低的整个百万的）输出到输出文件，并读出从在其位置该组的下一个。

然后就继续选择最低的10，写出来，并从同一组替换它。通过这种方式，最终的输出是整个一百万个条目的排序列表。

Answer 2

尝试此页：Sorting Algorithms。除了展示几种算法的漂亮动画之外，它还解释了它们如何工作以及它们的复杂性。

Answer 3

退房external merge sort算法。