简单的答案是，这个问题没有简单的答案。答案很多，其中大多数都相当复杂-Knuth第3卷（例如一个例子）为此花了大量篇幅。

仔细查看已完成的操作时，显而易见的一件事是，您 真的
想最大程度地减少在初始排序过程中创建的运行次数，并最大化每次运行的时间。为此，您通常希望读入尽可能多的数据以放入内存，但您不希望仅将其排序并写出来，而是要将其放入堆中。然后，当您写出每条记录时，您将读入另一条记录。

然后，您检查该记录是在刚刚写出的记录之前还是之后进行排序。如果要对其进行排序，请将其插入到堆中，然后继续。如果之前可以排序，则将其插入第二个堆。

当第一个堆完全为空，而第二个堆占用了所有内存时，您就停止向当前运行添加记录。此时，您将重复此过程，将新运行写入新文件。

在初始阶段，这通常会产生更长的中间运行时间，因此合并它们的工作量大大减少。假设输入记录是随机的，则可以预期这将使每次运行的长度大约增加一倍-
但是，即使对输入进行了部分排序，这也可以利用现有的顺序来延长运行长度。

顺便说一句，我当然没有发明它-我可能首先在Knuth中读过它，但是也许在 算法+数据结构=程序 （Niklaus
Wirth）中-都对此进行了讨论。克努斯（Knuth）在1954年在麻省理工学院（MIT）的硕士论文中首次将该方法归功于“ H.苏厄德（H.
Seward）”。如果您有克努斯（Knuth）的第二版，请参阅第3卷254页。我没有第三版的副本版，所以我没有相应的页码。