合并排序法

合并排序（Merge Sort）就是将两个或多个有序表合并成一个有序表。将两个有序表合并成一个有序表的过程称为二路合 并。对于一个原始的待排序序列，往往可以通过分割的方法归结为多路合并排序。

算法描述 

二路合并排序的基本思想是：

对于两个有序表合并，初始时，把含有n个节点的待排序序列看做由n个长度为1的有序子表所组成，将它们依次两两合并，得到长度为2的若干有序子表，再对这些子表进行两两合并，得到长度为4的若干有序子表……一直 重复到长度为n，排序完成。

合并排序过程 使用二路合并排序法进行排序时，需要占用较大的辅助空间，辅助空间的大小与待排序序列一样多。 下面以一组待排序的数据演示合并排序的过程，假设有9个需要排序的数据序列如下：

 69，65，90，37，92，6，28，54，34

提示 为了演示不能完整划分子表的情况，本例中使用了9个数据。

使用合并排序法进行排序的过程如上图所示，具体排序过程如下： 

（1）首先将9个原数据看成9个长度为1的有序表（只有一个数据，肯定是有序的）。 

（2）将这9个有序表两两合并，即将第1、2个合并在一起，第3、4个合并在一起……第9个没有合并的，就单独放在那里， 直接进入下一遍合并。 

（3）经过第1遍的合并，得到长度为2的有序表序列，再将这些长度为2的有序表序列进行两两合并。 

（4）经过第2遍合并，得到长度为4的有序表序列，再将这些长度为4的有序表进行两两合并。 

（5）经过第3遍合并，得到长度为8的有序表序列，以及最后只有一个元素的序列，将这两个序列进行合并，即可完成合并 排序。

提示 二路合并排序过程中需要进行若干遍的合并，每一遍合并包括若干次二路合并。

2．合并相邻有序表：

如果需合并的两个有序表保存于数组A中，其中一个序列保存在下标从s到m的数组元素中，另一个序列保存在下标从m+1到n 的数组元素中。合并的结果保存在数组R（该数组为辅助空间）中。用变量i、j分别指向两个系列中需要比较的元素，变量k指向 数组R中的序号，表示下一个要保存数据的位置，合并过程如下：

（1）取第1个系列的第i个元素A[i]，与第2个系列的第1个元素A[j]比较。 

（2）若A[i]≤A[j]，则将A[i]复制到R[k]中，使i和k分别增加1。 

（3）若A[i]>A[j]，则将A[j]复制到R[k]中，使j和k分别增加1。 

（4）重复步骤1至3，直到一个序列复制完为止。 

（5）将另一个序列中未比较的数据复制到R的剩余位置。 

这样，就完成了相邻有序表的合并排序操作。

3．完成一遍完整合并

设数组A中的n个记录已分成若干个长度为len的有序表，最后一个有序表的长度可能小于len，要求将这些表两两合并成一些 长度为2*len的有序表，并把结果保存到数组R中。当n不是2*len的整数倍时，可能有以下两种情况： 

一是剩下一个长度为len的表和一个长度小于len的表，由于二路合并算法不要求待合并的两个有序表必须有相同的长度，可 将最后这两个表进行合并，只是合并后的有序表的长度小于2*len。

另一种情况是只剩下一个有序表，其长度小于等于len，则将其直接复制到R中对应区间即可。

4．合并排序 

整个二路合并排序过程需要进行若干遍排序操作，第一遍排序时，有序表的长度len为1，以后每进行一遍排序将len的长度增 加一倍。假设需排序的n个数据存在数组A中，合并过程中将使用一个辅助数组R。第一遍合并时，数组A中为需要进行合并排序 的数据，将合并的结果保存到数组R中；第二遍合并时，数组R中需要进行合并排序的数据，将合并的结果保存到数组A中；如此 反复进行，直到n个记录成为一个有序表时为止。