算法设计与分析

二路归并排序的基本思想

设数组a中存放了n个数据元素，初始时把它们看成是n个长度为1的有序子数组，然后从第一个有序子数组开始，把相邻的有序子数组两两合并，得到[n/2]个长度为2的新的有序子数组（当n为奇数时，最后一个新的有序子数组的长度为1）。对这些新的有序子数组再进行两两归并。如此重复，直到得到一个长度为n的有序数组为止。

一次二路归并排序算法的目标是把若干个长度为k的相邻有序子数组从前、向后进行两两归并，得到个数减半的长度为2k的相邻有序子数组。算法设计中要考虑的一个问题是：若元素个数为2k的整数倍，则两两归并正好完成n个数据元素的一次二路归并；若元素个数不为2k的整数倍，则当归并到最后一组时，剩余的元素个数会不足2k个，这时的处理方法是：

① 若剩余的元素个数大于k而小于2k，则把前k个元素作为一个子数组，把剩余的元素作为最后一个子数组。

② 若剩余的元素个数小于k时，也即剩余的元素个数只够一组时，则不用再进行两两归并排序。

二路归并排序的复杂度分析

对n个元素进行一次二路归并排序时，归并的次数约为lbn，任何一次的二路归并排序元素的比较次数都约为n-1，所以，二路归并排序算法的时间复杂度为O(nlbn)。

二路归并排序时使用了n个临时内存单元存放数据元素，所以，二路归并排序算法的空间复杂度为O(n)。

由于二路归并排序算法是相邻有序子表两两归并，对于关键字相同的数据元素，能够保证原来在前边的元素排序后仍在前边，因此，二路归并排序算法是一种稳定的排序算法。

前边讨论过的几个时间复杂度为O(nlbn)的排序算法都是不稳定的排序算法，而二路归并排序算法不仅时间复杂度是O(nlbn)，而且还是一种稳定的排序算法。这是二路归并排序算法的最大特点。