归并排序算法的编码和优化

在大型公司的面试过程中，排序是必问的知识。本篇内容来自《算法（第4版）》 — — Robert Sedgewick， Kevin Wayne

概念

归并排序的实现我是这样来描述的：先对少数几个元素通过两两合并的方式进行排序，形成一个长度稍大一些的有序序列。然后在此基础上，对两个长度稍大一些的有序序列再进行两两合并，形成一个长度更大的有序序列，有序序列的的长度不断增长，直到覆盖整个数组的大小为止，归并排序就完成了。

递归和循环

归并排序有两种实现方式： 基于递归的归并排序和基于循环的归并排序。（也叫自顶向下的归并排序和自底向上的归并排序）

这两种归并算法虽然实现方式不同，但还是有共同之处的：

1. 无论是基于递归还是循环的归并排序， 它们调用的核心方法都是相同的：完成一趟合并的算法，即两个已经有序的数组序列合并成一个更大的有序数组序列 （前提是两个原序列都是有序的！）

2. 从排序轨迹上看，合并序列的长度都是从小（一个元素）到大（整个数组）增长的。

单趟归并算法 单趟排序的实现分析

下面我先介绍两种不同归并算法调用的公共方法， 即完成单趟归并的算法。（两个已经有序的数组序列合并成一个更大的有序数组序列）

在开始排序前创建有一个和原数组a长度相同的空的辅助数组aux

单趟归并的过程如下：

1. 首先将原数组中的待排序序列拷贝进辅助数组的相同位置中，即将a[low…high]拷贝进aux[low…high]中

2. 辅助数组aux的任务有两项：比较元素大小， 并在aux中逐个取得有序的元素放入原数组a中 （通过1使aux和a在low-high的位置是完全相同的！这是实现的基础）

3. 因为aux[low…high]由两段有序的序列：aux[low…mid]和aux[mid…high]组成， 这里称之为aux1和aux2,我们要做的就是从aux1和aux2的头部元素开始，比较双方元素的大小。将较小的元素放入原数组a中（若a[0]已被占则放在a[1]…依次类推），并取得较小元素的下一个元素， 和另一个序列中较大的元素比较。因为前提是aux1和aux2都是有序的，所以通过这种方法我们能得到更长的有序序列

4. 如果aux的两段序列中，其中一段中的所有元素都已”比较”完了, 取得另一段序列中剩下的元素，全部放入原数组a的剩余位置。

过程3和4的实现方法

• 设置两个游标 i 和 j 用于“元素比较” （在aux中进行）：变量,i 和 j，分别代表左游标和右游标，开始时分别指向aux[low]和aux[mid]
• 设置游标k用于确定在a中放置元素的位置（在a中进行），k在开始时候指向a[low]
• 总体上来说i, j, k的趋势都是向右移动的

结合上面的过程3， 比较 i 和 j 当前所指的aux中的元素的大小， 取得其中比较大的那个元素（例如上图中的i）,将其放入数组a中， 此时（在图中假设情况下）： i加1，左游标右移。 同时k也加1， k游标也向右移动。

结合上面的过程4， 在 i 和 j 都向右移动的过程中， 在图中假设情况下，因为j当前所指的元素（图中位置）大于左半边即a[low…mid]的所有元素，导致 i 不断增加（右移）且越过了边界（mid）, 所以这时候就不需要比较了，只要把j当前所指位置到high的元素都搬到原数组中，填满原数组中剩下的位置， 单趟归并就完成了， 在这一段过程中 j 连续加1，右游标连续右移。 同时k也连续加1， k游标也连续右移， 直到 j == high且k == high为止

基于上面的表述， 总结出单趟归并算法中最关键的4个条件判断情形：

• 左半边用尽（取右半边的元素）
• 右半边用尽（取左半边的元素）
• 右半边元素小于左半边当前元素（取右半边的元素）
• 右半边元素大于等于左半边当前元素（取左半边的元素）

单趟排序算法的代码

有了上面的解释，代码实现就不难了。

单趟排序的过程图解

为了更详细的描述单趟排序的过程，下面在上面的图A和图B的基础上给出每一步的图解：

我们要排序的序列是 2 4 5 9 1 3 6 7， 合并的前提是2 4 5 9 和 1 3 6 7都是有序的。 先比较aux中2和1的大小，因为2>1，所以将1放入a[0]。这时， 游标 i 不动， 游标 j 右移， 游标 k 右移。

比较aux中2和3的大小，因为2