并归排序法

归并就是将多个已排序的数列合成一个有序的数列。将两个有序序列合并为一个有序序列叫二路归并(merge)。归并排序就是利用"归并"技术来进行排序n长度为1的子序列,两两归并最后变为有序的序列。

一、两路归并算法1、算法基本思路

设有两个有序（升序）序列存储在同一数组中相邻的位置上，不妨设为A[l..m]，A[m+1..h]，将它们归并为一个有序数列，并存储在A[l..h]。

为了减少数据移动次数，不妨采用一个临时工作数组C，将中间排序结果暂时保存在C数组中，等归并结束后，再将C数组值复制给A。

归并过程中，设置p1，p2和p3三个指针，其初值分别指向三个有序区的起始位置。归并时依次比较A[p1]和A[p2]的关键字，取关键字较小的记录复制到C[p3]中，然后将被复制记录的指针p1或p2加1，以及指向复制位置的指针p3加1。

重复这一过程直至有一个已复制完毕，此时将另一序列中剩余数据依次复制到C中即可。

2）（1）自底向上的基本思想

自底向上的基本思想是：第1趟归并排序时，将数列A[1..n]看作是n个长度为1的有序序列，将这些序列两两归并，若n为偶数，则得到[n/2]个长度为2的有序序列；若n为奇数，则最后一个子序列不参与归并。第2趟归并则是将第1趟归并所得到的有序序列两两归并。如此反复，直到最后得到一个长度为n的有序文件为止。

上述的每次归并操作，均是将两个有序序列合并成一个有序序列，故称其为“二路归并排序”。