2路归并排序—Java语言描述，归并排序算法介绍

归并排序（Merge Sort）也是一种常用的排序方法，“归并”的含义是将两个或两个以上的有序序列合并成一个新的有序序列。假设初始序列含有n个记录，则可看成是n个有序子序列，每个子序列的长度为1，然后两两归并，得到一个长度为2（最后一个序列的长度可能小于2）的有序子序列；再两两归并，如此重复，直至得到一个长度为n的有序序列为止。每一次归并过程都称为一趟归并排序，这种排序方法称为2路归并排序。2路归并排序的核心是将相邻的两个有序序列归并成一个有序序列。类似地，也可以有“3路归并排序”或“多路归并排序”。

【例9.7】设待排序的记录初始序列为｛20，50，70，30，10，40，60｝，用2路归并排序法对其进行排序。

下面来介绍归并排序的算法。

①两个有序序列的归并算法

设线性表R[low，…，m]和R[m+1，…，high]是两个已排序的有序表，且存放在同一数组中相邻的位置上，现将它们合并到一个数组R1中，则合并过程如下：

（1）比较两个线性表的第一个记录，将其中关键字值较小的记录移入表R1中（如果关键字值相同，可将R[low，…，m]的第一个记录移入R1中）。

（2）将关键字值较小的记录所在线性表的长度减1，并将其后继记录作为该线性表的第一个记录。

（3）反复执行过程（1）和（2），直到两个线性表中的一个成为空表，然后将非空表中剩余的记录移入R1中，此时R1则成为一个有序表。

算法描述如下：

②一趟归并排序算法

一趟归并排序是将若干个长度为m的相邻的有序子序列，由前至后依次两两进行归并，最后得到若干个长度是2m的相邻有序的序列，但可能存在最后一个子序列的长度小于m，以及子序列的个数不是偶数这两种情况：(www.xing528.com)

（1）若剩下一个长度为m的有序子表和一个长度小于m的子表，则使用前面提到的有序归并的方法归并排序。

（2）若子序列的个数不是偶数，只剩下一个子表，其长度小于或等于 m，则此时不调用算法Merge（），只需将其直接放入数组R1中，准备进行下一趟归并排序即可。

一趟归并排序算法描述如下：

③二路归并排序算法

二路归并排序其实上就是不断调用一趟归并排序，只需要在子序列的长度m小于n时，不断地调用一趟归并排序算法MergePass（）即可。每调用一次，m增大一倍，其中，m的初值是1。

其算法如下：

在算法中，每趟排序的数据存储在临时的顺序表R1中，所以在每趟排序结束后，需要将排序的结果再返回到R中。

在上述算法中，第二个调用语句MergePass前并未判定m>n是否成立，若成立，则排序已完成，但必须把结果从R1复制到R中。而当m>n时，执行MergePass（R1，R，m，n）的结果正好是将R1中唯一的有序文件复制到R中。

显然，第i趟归并后，有序子文件长度为2。因此，对于具有n个记录的文件排序，必须做趟归并，每趟归并所花的时间是O（n），所以二路归并排序算法的时间复杂度为O（nlog2n）。算法中辅助数组R[1]所需的空间复杂度是O（n），所以二路归并排序是稳定的排序方法。