排序算法之归并排序
基本概要
要想弄理解归并排序，首先我们要知道分治的思想。严格说来，分治并不能算是一个算法，它是凌驾于算法之上的一种思想，很多具体的算法都是基于这个思想而产生的，比如今天的主角归并排序，还有后面要将的快速排序，以及之前我们介绍的 快速选择。
分治大体说来就两部分，分 和 治。我们首先将一个大的问题拆分成小问题，再对小问题进行解决，等到每个小问题都解决完毕后，大问题也就解决完毕了。那么分治这个思想一般会被用在什么场合比较合适呢？有以下几点可供参考：
- 问题可拆分。如果问题不可分，那么何谈分治？我们直接就被卡在分的阶段，这种情况下分治就没法进行下去了。
- 拆分后的小问题可通过相同的策略解决。拆分后的小问题需要有同一性，这样在 “治” 的阶段我们才知道如何去解决。一般来说，递归是实现分治最自然且常用的手段。
- 小问题的解决等同于大问题的解决。如果说每个小问题的答案没法等同或推导出整个问题的答案，那么分治也就没办法得出问题的解，这样的问题也不适合分治。
有了上面这些关于分治的简单介绍，我们再回过头来看归并排序算法。算法的最终目的，也就是整个问题是将一个数组或者元素集合按序排列。
首先考虑的是 这个问题可拆分吗？很明显，一个数组可以一分为二拆分成左右两个数组，其中每个数组又可以一分为二地拆分下去。这样一个大的数组的排序就可以拆分成若干个小的数组的排序，由此可见，问题是可拆分的。
接着考虑 拆分后的小问题是否可通过相同的策略解决？ 通过上面的问题拆分策略，我们可以看出，一个数组拆分到最后不能继续再分，其实就是单个元素，单个元素本身就是排好序的，无需再排，现在的问题的是如何将这些拆分后的元素合并成拆分前的数组？这个策略是否对所有的情况均成立？
现在问题就变成了，我们有两个排序好的数组，如何将这两个数组合并成新的数组，并且保证新的数组也是排序好的？ 策略其实不难想到，思想如下面代码所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int[] merge(int[] a, int[] b, int[] newArr) {
int i = 0, j = 0, k = 0;
while (i < a.length && j < b.length) {
if (a[i] > b[j]) {
newArr[k++] = b[j++];
} else {
newArr[k++] = a[i++];
}
}
while (i < a.length) {
newArr[k++] = a[i++];
}
while (j < b.length) {
newArr[k++] = b[j++];
}
return newArr;
}
那么 小问题的解决是否等同于大问题的解决？ 这是肯定的，上面的合并策略适用于任意大小的数组的合并。通过递归向下拆分，然后再向上合并，最终得到的就是排序好的数组。
了解了基本的思想，现在我们就不难理解归并了。它其实说的是分治中的 “治”，因为 “分” 没什么好说的，就是一分为二，一个数组拆分到最后就会是单个元素，在 “治” 的过程中，我们将两个排序好的数组归并在一起，这样就解决了拆分前的问题（比如将两个单个元素合并在一起就将拆分前的二元组给排序好了，两个二元组合并后又将之前的四元组排序好了，以此类推到最后我们就会将整个数组排序好）。
具体实现
如果清楚了上面的分治思想以及合并的思路，那么归并排序的实现就没有任何的难点了。但这里其实还有一个小小的优化，通过前面的合并的示例代码我们知道，合并的时候我们还需要一个新的数组，但如果在递归的每个阶段我们都创建一个新的数组，这势必会造成空间的浪费，因此我们可以提前将这个数组创建出来，递归的时候直接使用即可。具体实现如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public static <AnyType extends Comparable<? super AnyType>> void mergeSort(AnyType[] arr) {
mergeSort(arr, (AnyType[]) new Comparable[arr.length], 0, arr.length - 1);
}
public static <AnyType extends Comparable<? super AnyType>> void mergeSort(AnyType[] arr, AnyType[] tmpArr, int left, int right) {
if (left < right) {
int center = (left + right) / 2;
mergeSort(arr, tmpArr, left, center);
mergeSort(arr, tmpArr, center + 1, right);
merge(arr, tmpArr, left, center + 1, right);
}
}
public static <AnyType extends Comparable<? super AnyType>> void merge(AnyType[] arr, AnyType[] tmpArr, int leftPos, int rightPos, int rightEnd) {
int leftEnd = rightPos - 1;
int tmpPos = leftPos;
int numElements = rightEnd - leftPos + 1;
while (leftPos <= leftEnd && rightPos <= rightEnd) {
if (arr[leftPos].compareTo(arr[rightPos]) <= 0) {
tmpArr[tmpPos++] = arr[leftPos++];
} else {
tmpArr[tmpPos++] = arr[rightPos++];
}
}
while (leftPos <= leftEnd) {
tmpArr[tmpPos++] = arr[leftPos++];
}
while (rightPos <= rightEnd) {
tmpArr[tmpPos++] = arr[rightPos++];
}
for (int i = 0; i <= numElements; i++, rightEnd--) {
arr[rightEnd] = tmpArr[rightEnd];
}
}
在 mergeSort 函数中我们对数组进行了 先分后合 的操作，最主要的合并在 merge 函数中，这里的思想其实和之前的示例代码是一样的，唯一的区别是在函数的最后，我们将临时数组中的结果拷贝到了需要被排序的数组中。
算法分析
回过头来看归并排序，从思想到实现都是分治的标准案例。现在我们来看看其时间复杂度，对于一个元素个数为 N 的数组，假设整个算法的时间复杂度为 $ T(N) $，由于每次拆分都是将数组均匀地分成两部分，每次合并操作的时间复杂度是 O(N) 因此我们可以得到下面这个式子：
将等式两边除以 N 可得：
\[\frac{T(N)}{N} = \frac{T(N/2)}{N/2} + 1\]以此类推可得：
\[\frac{T(N/2)}{N/2} = \frac{T(N/4)}{N/4} + 1\] \[\frac{T(N/4)}{N/4} = \frac{T(N/8)}{N/8} + 1\] \[...\] \[\frac{T(2)}{2} = \frac{T(1)}{1} + 1\]将上述所有等式相加，中间的一些项就两两相互抵消，就可得到：
\[\frac{T(N)}{N} = \frac{T(1)}{1} + logN\]因而：
\[T(N) = NlogN\]由此可得，归并排序的时间复杂度为 O(NlogN)。
但是归并排序的空间复杂度是 O(N)，这是这个排序算法的一个不太完美的地方，在合并的过程中，我们需要借助一个临时的数组来存放合并后的结果，然后再将这个结果拷贝回原数组，这里面也有时间的开销，只不过这个时间的开销并不显示在时间复杂度上。
当然了，没有一个算法是完美的，虽说归并排序需要一个额外的数组，在合并的过程中也需要拷贝等额外操作，但是它是所有的基于比较的排序中所需比较次数最少的排序。基于这些特性，归并排序非常适合类似 Java 这样的语言，因为 Java 的比较是基于类似 Comparable 这样的类，元素比较的开销比较大，但是 Java 的拷贝是基于引用而不是整个对象，因而拷贝的开销比较小。其实 Java 的内定排序算法就是归并排序。通过整体的感觉，你也可以觉察到归并排序的气质和 Java 这门语言的气质比较一致，按照步骤一步步实现下来就可以获得期望的结果，这里面除了啰嗦一点，并没有太多容易出错的点。
但是对于 C++ 这样的语言，归并排序就不太适合了，C++ 对象的拷贝所需的开销很大，但是因为有编译器的优化，元素的比较开销比较小，这和归并排序的特性是相反的，C++ 内定的排序算法为快速排序，这个算法我们后面会介绍，不得不说快速排序的气质和 C++ 也是非常相似的，灵活且多变，实现上面细微的差别会导致最后的结果大相径庭，而且有着各种各样的优化，快速排序的最佳实践到目前为止也无人知晓，因为理论上来说还可以更优。