8.5.1　2－路归并排序

归并排序主要是2－路归并排序。通常，我们将两个有序段合并成一个有序段的过程称为2－路归并。

2－路归并排序：可以把一个长度为n的无序序列看成是n个长度为1的有序子序列，首先做两两归并，得到n／2个长度为2或1的有序子序列；再做两两归并……如此重复，直到最后得到一个长度为n的有序序列。例如图8－13为2－路归并排序的一个例子。

图8－13 2－路归并排序示例

1.2－路归并算法

2－路归并排序中的核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列，其算法如下。

假设记录序列被存储在一维数组a中，且a［s］～a［m］和a［m＋1］～a［t］已经分别有序，现将它们合并为一个有序段，并存入数组a1中的a1［s］～a1［t］。

合并过程如下：

（1）设置三个整型变量k、i、j，用来分别指向a1［s...t］中当前应该放置新记录的位置、a［s］～a［m］和a［m＋1］～a［t］中当前正在处理的记录位置。初始值应该为：

（2）比较两个有序段中当前记录的关键字，将关键字较小的记录放置a1［k］，并修改该记录所属有序段的指针及a1中的指针k。重复执行此过程直到其中的一个有序段内容全部移至a1中为止，此时需要将另一个有序段中的所有剩余记录移至a1中。其算法实现如下：

算法8.12 2－路归并排序算法

2.归并排序的递归算法

归并排序方法可以用递归的形式描述，即首先将待排序的记录序列分为左右两个部分，并分别将这两个部分用归并方法进行排序，然后调用2－路归并算法，再将这两个有序段合并成一个含有全部记录的有序段。

算法8.13 归并排序递归算法