归并趟数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值过大时,虽然归并趟数会减少,但读写外存的次数会增加。