9.7　归并排序

归并排序是通过不断地把将两个或两个以上的较小有序序列合并成一个较大的有序序列的一种排序方法。

归并排序的基本思想是:假设待排序记录序列长度为n,初始时把它们看作是n个长度为1的有序子序列,然后从第一个子序列开始对这些相邻的子序列进行两两合并,即第1个序列与第2个序列合并,第3个子序列与第4个子序列合并,依此类推,将得到（int）（n/2）个长度为2的有序子序列,可能还有1个长度为1的子序列,这个过程被称为一趟归并排序。然后再继续对这些长度为2或1的有序子序列进行类似上述的两两合并过程,并如此重复下去,直到合并成一个长度为n的有序序列为止。

下面通过具体的例子来进行说明。

【例9－6】　初始序列为{23,56,42,37,15,84,72,27,18}用二路归并排序法排序。

排序后的结果为{15,18,23,27,37,42,56,72,84},整个归并过程如图9－5所示。

图9－5　二路归并过程

由上述排序过程可知,有序子序列总是进行相邻的两两归并,因此归并排序也称为二路归并排序。多于二路的归并排序方法与二路归并排序方法在基本思想上是类似的。

二路归并排序的核心是将相邻的两个有序序列合并成一个有序的序列。假设aa[1,…,m]和aa[m＋1,…,n]是两个相邻的有序序列,合并后产生的有序序列用数组bb[1,…,n]来存放,数组元素分别为（bb[1],bb[2],…,bb[m],bb[m＋1],bb[m＋2],…,bb[n]）。假设有i,j,k是分别指向三个序列当前元素的指针。开始的时候,i＝1,j＝m＋1,k＝1,依次扫描两个已知子序列,如果有aa[i].key≤aa[j].key,则将aa[i]复制到bb[k]中,并使i与k指针各自加1；否则将aa[j]复制到bb[k]中,且j与k指针各自加1,再继续扫描比较。当其中一个已知序列已全部复制到bb中,就将另一个已知序列中的剩余元素依次复制到bb中,这样就将两个有序序列合并为一个有序序列。

这一合并过程的相应算法可描述如下。

在上述合并算法的基础上,要实现二路归并排序算法可以用迭代法和递归算法两种方法来进行。

接下来首先来讨论如何完成一趟归并排序。从例9－6及之前的归并算法的描述可知,每一趟排序都是从前到后,依次将相邻的两个有序子序列进行合并,并且除最后一个子序列外,其余每个子序列的长度都相同。设这些长度相等的子序列的长度为len,则一趟归并排序的过程为:从R[1]开始,依次将子序列R[i,…,i＋len－1]和R[i＋len,…,i＋2len－1]进行归并,每次归并两个子序列后,i向后移动2len个位置,即i＝i＋2len；若归并扫描到最后,剩下的元素不足两个子序列长度时,分以下两种情况进行处理。

（1）若剩下的元素个数大于一个子序列长度len时,则调用合并算法,将一个长度为len的子序列和剩下的不足len个元素的子序列进行归并。

（2）若剩下的元素个数小于或等于一个子序列长度len时,则只需将剩下的元素依次复制到归并后的序列中。

根据上面描述的步骤,一趟归并排序的算法如下所示。

在开始归并排序时,每个记录可以看成是一个长度为1的有序子序列,利用二路归并算法对这些有序子序列逐趟进行归并,每一趟归并后有序子序列的长度均扩大一倍（最后一个子序列可能例外）,当有序子序列的长度与整个记录序列长度相等时,也即是所有待排记录都合并到一个有序序列的时候,整个记录序列排序结束。其中,aa[1,…,n]为初始待排序序列,bb[1,…,n]作为辅助空间,与aa[1,…,n]轮流存放某一趟排序结果。排序结束后,aa[1,…,n]中为已排好序的记录序列。因此,这个二路归并排序的迭代算法描述如下。

如果采用分治思想来实现归并排序,可采用二路归并排序的递归算法。其基本思路是:先将整个待排序列划分为两个长度基本相等的子序列,然后分别对两个子序列进行二路归并排序,使两个子序列分别有序,最后再将这两个有序子序列合并成为一个完整的序列,这样就得到了二路归并排序。其递归算法描述如下。

如果要将整个待排序记录aa[1,…,n]归并排序到bb[1,…,n]中,则只需调用MergeSort2（aa,bb,1,n）即可。

【算法分析】

（1）时间复杂度　从上述二路归并排序过程来看,对于具有n个待排序记录的归并次数显然是log₂n,每一趟归并的时间复杂度为O（n）,所以归并排序的时间复杂度无论是在最好情况下还是在最坏情况下均为O（nlog₂n）。

（2）空间复杂度　从该排序过程还可以看出,归并排序需要的辅助空间与待排序记录的数量相等,所以归并排序的空间复杂度为O（n）。

（3）稳定性　从排序的稳定性看,二路归并排序是一种稳定的排序方法。