开篇
上篇聊到的堆排序仅用线性对数级别的时间复杂度 O(n log n) 和常数级别的额外辅助空间即可将一个数组排序，已然十分高效。这篇我们来聊一种同样高效但要更古老的排序算法——归并排序。
正文
何为归并排序
此算法于 1945 年由计算机科学的祖师爷——约翰·冯·诺伊曼（对就是那个大名鼎鼎的冯·诺依曼）首次提出，看年代确实挺古老的！
将两个已经（整体）有序的数组合并成一个更大的有序数组，这就叫归并：
原始数组：[6, 5, 3, 1, 8, 7, 2, 4]
---------------------|
---------------------|
左半排序：[1, 3, 5, 6]|------------
右半排序：------------|[2, 4, 7, 8]
归并操作：[1, 2, 3, 4, 5, 6, 7, 8]
自顶向下的递归实现
归并排序是算法里面分治法的典型应用，一种经典的实现是采用递归的方法自顶向下分而治之是
来张动图具象化展示下以帮助理解，图源维基百科：
具体逻辑如此，下面我们直接上代码（Java）来看看归并排序到底是怎么一回事，实现中有个将两个有序数组归并成一个有序数组的操作我们将其抽象成一个单独的工具方法，命名为 merge（其实是将当前数组两个有序的子数组归并）。一点注意，此方法需要额外的辅助空间：
/**
* @param array:待归并数组，我们需要将此数组的[start, mid] 和 [mid + 1, end] 两个已经有序的子数组归并起来
* @param aux:辅助数组，完成归并操作的额外辅助空间，其大小应和 array 一致
* @param start:归并区间起始位置，inclusive
* @param mid:归并区间第一个子数组的有边界，inclusive
* @param end:归并区间终止位置，inclusive
*/
private static void merge(int[] array, int[] aux, int start, int mid, int end){
//将 array 的 [start, mid] 和 [mid + 1, end] 两个已有序的子数组归并
int s1 = start;//start1
int s2 = mid + 1;//start2
for (int i = start; i <= end; i++){//拷贝待排序数组
aux[i] = array[i];
}
//开始归并两个(子)数组
for (int i = start; i <= end; i++){
if (s1 > mid){ //第一个子数组(左半边)已遍历完
array[i] = aux[s2++];
}else if (s2 > end){ //第二个子数组(右半边)已遍历完
array[i] = aux[s1++];
}else if (aux[s1] > aux[s2]){//平凡情况，取右半边元素
array[i] = aux[s2++];
}else { //平凡情况，取左半边元素
array[i] = aux[s1++];
}
}
}
/**
* <p>归并排序自顶向下的递归实现</p>
* @param array:待排序数组，将数组的 [start, end] 区间排序
* @param aux:辅助数组，完成归并操作的额外辅助空间，其大小应和 array 一致
* @param start:待排序区间起始位置，inclusive
* @param end:待排序区间终止位置，inclusive
*/
public static void sortMerge(int[] array, int[] aux, int start, int end){
if(end <= start){//递归结束条件
return;
}
int mid = start + (end - start)/2;//归并左半部分的终止位置，右半部分的起始位置自然是 mid + 1
sortMerge(array, aux, start, mid);//左半部分排序
sortMerge(array, aux, mid + 1, end);//右半部分排序
merge(array, aux, start, mid, end);//归并两个已排序的子数组
}
其中 sortMerge 方法的递归逻辑可能不是那么容易理解，需要好好消化一下。以数组 [6, 5, 3, 1, 8, 7, 2, 4] 为例，我们一起来捋下其排序递归操作的函数调用轨迹来帮助理解：
-------------a = [6, 5, 3, 1, 8, 7, 2, 4]
-------------sortMerge(a, aux, 0, 7)//为此数组初始调用归并排序，设辅助数组为 aux
-------------
左半部分排序：sortMerge(array, aux, 0, 3)----------------------->瞧见没，典型的分而治之
------------- sortMerge(array, aux, 0, 1)
------------- merge(array, aux, 0, 0, 1)
------------- sortMerge(array, aux, 2, 3)
------------- merge(array, aux, 2, 2, 3)
右半部分排序：sortMerge(array, aux, 4, 7)----------------------->瞧见没，典型的分而治之
------------- sortMerge(array, aux, 4, 5)
------------- merge(array, aux, 4, 4, 5)
------------- sortMerge(array, aux, 6, 7)
------------- merge(array, aux, 6, 6, 7)
归并结果----：merge(array, aux, 0, 3, 7)
为避免递归带来的额外开销，还请读者自行把上面的代码改造成非递归版本。
上面提到了自顶向下这种说法，仔细观察算法的执行过程，我们是将一个大问题分割成（两个）小问题来分别解决，然后用所有小问题的解来得到整个大问题的解（典型的分而治之）。其实反之亦是一种不错的实现思路，也即自底向上：首先我们进行两两归并（把数组每个元素看成一个大小为 1 的子数组，将相邻两个子数组归并到一起，每次归并两个元素）然后四四归并、八八归并（粒度越来越粗），直至数组整体有序。
自底向上的嵌套循环实现
/**
*<p>归并排序自底向上的嵌套循环实现</p>
* @param array:待排序数组，将数组的 [start, end] 区间排序
* @param aux:辅助数组，完成归并操作的额外辅助空间，其大小应和 array 一致
*/
public static void sortMerge_(int[] array, int[] aux){
for (int size = 1; size < array.length; size <<= 1){//子数组的大小每次都翻倍
//根据当前每个子数组的大小 size，按顺序对相邻两个子数组应用归并操作，注意每个子数组在当前 size 下只参与一次归并操作
for (int start = 0; start < array.length - size; start += size + size){
int end = start + size + size - 1;
//这里的 merge 方法跟上面的自顶向下的一致
merge(array, aux, start, start + size - 1, Math.min(end, array.length - 1));//最后一次归并时，第二个子数组可能比第一个体积要小，或者跟第一个相等，我们的归并操作支持为两个大小不同的数组应用
}
}
}
上面的代码跟我们一开始实现的自顶向下版本是基本等价的，可以看到其代码要精简许多。还是以数组 [6, 5, 3, 1, 8, 7, 2, 4] 为例，其方法执行轨迹如下：
-------------自底向上对数组归并排序
-------------a = [6, 5, 3, 1, 8, 7, 2, 4]
-------------sortMerge(a, aux)//自底向上归并排序，设辅助数组为 aux
-------------
------------- size = 1
------------- merge(array, aux, 0, 0, 1)
------------- merge(array, aux, 2, 2, 3)
------------- merge(array, aux, 4, 4, 5)
------------- merge(array, aux, 6, 6, 7)
------------- size = 2
------------- merge(array, aux, 0, 1, 3)
------------- merge(array, aux, 4, 5, 7)
-------------size = 4
-------------merge(array, aux, 0, 3, 7)
-------------数组已整体有序
*/
总结
如上所述，归并排序是建立在归并操作基础上的一种高效、稳定的排序算法，其时间复杂度恒为线性对数级别的 O(n log n) ，与输入无关。与我们之前讨论的排序算法不同，其实现需要额外的辅助空间，空间复杂度最坏为线性级别的 O(n)。
尾巴
因其高效性，归并排序是当下应用非常广泛的排序算法，很多语言的的标准函数库中涉及到排序的地方一般都有其实现（比如Java）。那归并排序是应用最广泛的排序算法吗？答案是否定的，下篇我们就来聊一种更加高效，且是目前应用最广泛的排序算法——快速排序（你看这名字！）。
