在二路归并排序中，对n个元素进行归并的趟数为()。

在归并排序中，进行每趟归并的时间复杂度为（①)，整个排序过程的时间复杂度为（②)，空间复杂度为（③)。

假定一组记录的排序码为（46，79，56，38，40，80)，对其进行归并排序的过程中，第二趟归并后的结果为（)，

对20个记录进行归并排序时，共需要进行（①)趙归并，在第三趟归并时是把长度为（②)的有序表两两归并为长度为（③)的有序表。

结束后关键字序列的状态。

①直接插入排序;

②折半插入排序;

③希尔排序(增量选取5，3，1);

④冒泡排序;

⑤快速排序;

⑥简单选择排序;

⑦二路归并排序。

试问：

(1)可以建立多少个初始归并段？每个初始归并段有多少个记录？存放于多少个块中？

(2)应采用几路归并？请写出归并过程及每趟需要读写磁盘的块数。

（1)若使用多路归并执行3趟完成排序，那么应取的归并路数至少应为多少？（2)如果操作系统要求一个

(1)若使用多路归并执行3趟完成排序，那么应取的归并路数至少应为多少？

(2)如果操作系统要求一个程序同时可用的输入输出文件的总数不超过15个，则按多路归并至少需要几趟可以完成排序？如果限定这个趟数，可取的最低路数是多少？

试设计一个算法，对其进行二路归并排序，要求不移动结点中的元素，只改各链结点中的指针，排序后r仍指示结果链表的第一个结点。(提示：先对待排序的单链表进行一次扫描，将它划分为若干有序的子链表，其表头指针存放在一个指针队列中。当队列不空时重复执行，从队列中退出两个有序子链表，对它们进行二路归并，结果链表的表头指针存放到队列中。如果队列中退出一个有序子链表后变成空队列，则算法结束。这个有序子链表即为所求)。

设在磁盘上存放有375000个记录，做5路平衡归并排序，内存工作区能够容纳600个记录，为把所有记录排好序，需要做（)趟归并排序。

A、3

B、4

C、5

D、6

最佳归并树在外排序中的作用是（)。

A、完成k路归并排序

B、设计k路归并排序的优化方案

C、产生初始归并段

D、与锦标赛树的作用类似

设待排序的排序码序列为（12，2，16，30，28，10，16，20，6，18)，试分别写出使用以下排序方法每趟排序后

的结果，并说明做了多少次排序码比较，注意，后一个16附带一个“*”表明这是一个与前面某一个元素具有相同排序码值(16)的元素。

(1)直接插入排序

(2)希尔排序(增量为5，2，1)

(3)起泡排序

(4)快速排序

(5)简单选择排序

(6)锦标赛排序

(7)堆排序

(8)二路归并排序

(9)基数排序