|
|
|
有了m个初始归并段（都是有序段），便可进行k路归并了，即将k个初始归并段采用某种方法进行归并产生一个段，这样m个初始归并段便产生多个更大的段，然后对这些段再进行归并，如此下去，直到只生成一个段为止，这个段就是最后生成的归并段。
|
|
|
|
在内存里进行k路归并的方法很多。当归并路数k较大时，为了减少合并时的比较次数，常采用败者树进行合并的方法，其合并过程如下。
|
|
|
|
（1）用参加合并的k个有序段的第一个记录构造一棵初始败者树，该树中的根结点就是这k个记录中具有最小键值的记录。
|
|
|
|
|
|
（3）输出记录所在的有序段的下一个记录代替输出记录的位置，调整败者树。
|
|
|
|
（4）重复步骤（2）和（3），直到k个有序段的所有记录都输出为止。
|
|
|
|
对于总共有n个记录的k个有序段的合并过程，如果采用败者树进行合并，那么要选取键值最小的记录，在建立败者树时需要进行k-1次比较，此后每次调整败者树只要进行log2k次比较即可（因为树中保留了以前的比较结果）。所需总的比较次数为k+nlog2k，当n>>k时，总的比较次数约为nlog2k。
|
|
|
