每个关键字只有两次IO,一次读一次写

原理

每次选择归并段中最小的,但是要比写回外存的最大的要大

如果归并段满了,那么说明一趟置换选择结束。重复上一趟的步骤。直到形成初始归并段

上图得到了长度为 的初始归并段,那么如何协调归并段的顺序呢?

最佳归并树