7.7.3 多路平衡归并与败者树

归并趟数S=[logm R](向下取整)。从而增加归并路数m可以减少归并趟数S，进而减少访问外存的次数（I/O次数）。然而，当增加归并路数m时，内部归并时间将增加。做内部归并时，在m个元素中选择关键字最小的记录需要比较m-1次。每趟归并n个元素最多需要作（n-1）*(M-1)次比较，S趟归并总共需要的比较次数为：

S*(n-1)*(m-1)=[logmR]*(n-1)*(m-1)=[log2R]*(n-1)*(m-1)/[log2M]

其中的【log2R】*(n-1)在初始归并段个数R于记录个数n一定时是常数。而（m-1）/[log2M]随m增长而增长，则内部归并时间亦随m的增长而增长。这将抵消由于增大m而减少外存访问次数所得到的效益。因此不能使用普通的内部归并排序算法。

为了使内部归并并不受m的增大的影响，引入了败者树。败者树是对树形选择排序的一种变形，可以看作一棵完全二叉树。每个叶结点存放各归并段在归并过程中当前参加比较的记录，内部结点用来记忆左右子树中的“失败者”，而让胜者往上继续比较，一直到根结点。如果比较两个数，大的为失败者，小的为胜利者，则根结点指向的树为最小数。

因此m路归并的败者树深度为【log2M】,因此m个记录中选择最小关键字最多需要[log2M]次比较。所以总的比较次数为：

S*(n-1)*【log2 M】=【logm R】*（n-1）*【log2 M】=(n-1)*【log2 R】

因此，只要内存空间允许，增大归并路数m将有效地减少归并树的高度，从而减少I/O次数d,提高外部排序的速度。

值得说明的是，归并路数m的选择并不是越大越好。归并路数m增大时，相应地需要增加输入缓冲区个数。如果可供使用的内存空间不变，势必要减少每个输入缓冲区的容量，使得内外存交换数据的次数增大。当m值过大时，虽然归并趟数会减少，但读写外存的次数会增加。