若使用多路归并执行3趟完成排序

如果某个文件经内排序得到80个初始归并段，试问：
（1）若使用多路归并执行3趟完成排序，那么应取的归并路数至少应为多少？
（2）如果操作系统要求一个程序同时可用的输入/输出文件的总数不超过15个，则按多路归并至少需要几趟可以完成排序？如果限定这个趟数，可取的最低路数是多少？

这个最低路数，（若限定这个趟数，由S = 【logk80】 = 2，有80≤k2，可取的最低路数为9。即要在2趟内完成排序，进行9路排序即可。），80<=k2是怎么回事

在多路归并排序中，如果有n个有序归并段需要进行多路归并，则最少需要n路才能进行一次多路归并，否则就会出现某些归并段没有用到的情况，从而无法完成排序。

对于这个问题：

（1）如果使用3趟完成排序，则需要将80个初始归并段分别分成若干组，使得每组的归并段数量相同，且每组数量不超过k路（k为归并路数）。因为每趟多路归并的结果都是将归并段的数量变为原来的1/k，所以第一趟需要k路，第二趟需要k^2路，第三趟需要k^3路。根据题意，可得80/(k^3) <= k，即k^4 >= 80。所以，k的最小值为3。

（2）假设有S趟完成排序，那么每次多路归并后，归并段的数量都会变为原来的1/k。因此，多路归并的总次数为S，即(80/k^S) <= k。当限制S为2时，可得80/k^2 <= k，即k^3 >= 80，所以k的最小值为5。如果限定S为3，同理可得k的最小值为3。

因此，如果限定多路归并排序的趟数为2，则可取的最低路数为5；如果限定多路归并排序的趟数为3，则可取的最低路数为3。