问题
问答题
假设有12个初始归并段，其长度分别为85，68，62，9，18，60，20，3，6，8，44，30；现要进行4路外部归并排序，试画出表示归并过程的最佳归并树，并计算树的带权路径长度WPL。
答案
参考答案：[解答] 应加4-(12-1)n=rod(4-1)-1=1个虚段。
WPL=(3+6+8)×3+(9+18+20+30+44+60+62)×2+(68+85)×1=690
解析： 如何判定附加虚段的数目呢一般情况下，对k路归并而言，容易推导到，若(m-1)mod(k-1)=0，则不需要附加虚段，否则需要附加k-(m-1)mod(k-1)-1个虚段。换句话说，第一次归并为(m-1)mod(k-1)+1个路归并。其中mod表示求模运算符。
