9.6.4　归并排序

排序过程，如图9-42所示：

图9-42　归并排序

1.自顶向下的归并排序

排序思想：要将一个数组排序，可以先（递归的）将它分为两半分别排序，然后将结果归并起来。

对于自顶向下的归并排序的改进：

·由于归并排序的方法调用过于频繁，会产生过多的额外开销，所以归并排序在处理小规模问题时，比插入排序要慢。在用归并排序处理大规模数据时，使用插入排序来处理小规模的子数组，一般可使归并排序的运行时间缩短10％～15％。

·添加一个判断，如果data［mid］小于data［mid+1］，则数组已经有序，不需要进行归并操作。这样可大大减小有序子数组的运行时间。

·通过在递归调用的每个层次交换输入数组和辅助数组的角色，节省元素复制到辅助数组中的时间（空间不行）。即在递归中，数据从输入数组排序到辅助数组和从辅助数组排序到输入数组交替使用。

2.自底向上的归并排序

排序思想：先两两归并（把每个元素当成一个长度为1的数组），在四四归并，然后八八归并，一直下去。每轮归并中最后一次归并的第二个数组可能比第一个小（注意不要越界）。