归并与快排——2.归并排序
原创文章，转载请注明出处
1. 归并排序
归并排序是一个常用的时间复杂度为的排序算法，其排序的过程主要体现在“并”这个字上。
与传统的插入、冒泡排序不同，归并排序的思想并不是逐个遍历元素并且比较大小，而是使用了分治的思想。
说到这里不得不提一些题外话，分治的思想在系统设计中使用非常多，相比起来我认为实现归并排序的算法倒不是那么重要，而理解分治，才是思维上的重点，从归并到分治，再到MapReduce，有兴趣的朋友不难发现，这都是一脉相承的。
2. 原理分析
如果数组从中间分成两部分，而这两部分都是已经排序好的，那我们只需要将这两部分合并，在合并的过程中，分别顺序遍历两部分，将较小的数字取出放到一个新的数组中，当前部分的指针后移一位，这样直到将两个部分遍历完成，在新建的数组中便是已经排序好的结果了。
但是现实中基本没有天然的两部分已经排序好的数组，所以我们需要将两部分继续拆，拆成四个、八个。。。然后两两做合并操作。
上面的描述还是比较抽象，接下来我们从一个实际的例子来看归并排序一步一步都做了什么，现在有一个未排序过的数组：[1, 6, 2, 3, 7, 4]。
首先我们从数组中点将数组拆分为两部分，左边包含1, 6, 2，右边包含3, 7, 4。
归并1.jpg
但是左右两边并不是排序好的结果，所以我们进行第二次拆分。先看左边，继续选择中点在6, 2之间，而这时我们发现第二次拆分后左右两部分已经分别有序了[1, 6]， [2]。（在1和6之间应该还有一次拆分-合并操作，这里避免步骤太长先省略掉了）
归并2.jpg
那么我们接下来需要将[1, 6]和[2]两个部分进行合并，合并完成以后我们第一次分组的左半部分已经有序了。
归并3.jpg
但是我们发现右半部分还是无序的，所以我们需要重复和左半部分一样的操作，选取中点，拆分-合并，完成值后右半部分也变成有序的了。
归并4.jpg
最后我们需要将左右两部分再进行合并，完成以后整个数组也就排序完成了。
归并5.jpg
在上述的过程中，不断的涉及到拆分-合并，用一张完整的图来看，整体过程是这样的：
归并6.jpg
3. 代码实现
在代码实现上面，根据流程图与分析，我们可以很容易想到使用递归来实现归并排序，其递归公式可以写作：
mergeSort(left, right) = merge(mergeSort(left, half), mergeSort(half+1, right))
终止条件是left>=right，即不用继续分解了。
根据公式，我这里用Java实现了一个归并的代码供参考：
public class ArraySortUtils {
public static void mergeSort(int[] data) {
MergeSort.of(data).sort();
}
private static class MergeSort {
int[] array;
private MergeSort() {
}
static MergeSort of(int[] data) {
MergeSort mergeSort = new MergeSort();
mergeSort.array = data;
return mergeSort;
}
void sort() {
mergeSort(0, array.length - 1);
}
/**
* Time: nlog(n)
*
* @param left
* @param right
*/
void mergeSort(int left, int right) {
if (left == right) return;
int half = (left + right) / 2;
if (half != left) mergeSort(left, half);
if (half != right) mergeSort(half + 1, right);
merge(left, half, right);
}
void merge(int left, int half, int right) {
int[] temp = new int[right - left + 1];
int t = 0, i = left, j = half + 1;
while (i <= half && j <= right) {
if (array[i] <= array[j]) { // stable
temp[t++] = array[i++];
} else {
temp[t++] = array[j++];
}
}
int start = i, end = half;
if (j <= right) {
start = j;
end = right;
}
System.arraycopy(array, start, temp, t, end - start + 1);
System.arraycopy(temp, 0, array, left, temp.length);
}
}
}
4.性能评估
-
时间复杂度
如果我们使用表示当数据为量为n时归并排序所需要执行的时间，那么:
表示合并合并两个
数组所需的时间，是一个线性的时间，C和L均为常量级时间。
将这个公式继续拆分可以写成：
当我们拆分到最细时，应该是常数，也就是说
，也就是
最后可以分析出：
如果用大O表示法，那么归并排序的时间复杂度为： -
空间复杂度
归并排序的空间复杂度分析与时间复杂度类似，因为在合并函数merge()中，没两个子部分合并时都需要开辟临时空间用来合并。那么归并排序所需要的总空间与n的关系为：
与时间复杂度一样，我们可以得出归并排序需要使用的总空间复杂度为：
但是需要注意到的一点是这个关系为总的需要空间关系，也就是说，我们在执行过程中，之前使用过的临时空间可以被垃圾回收等机制给回收掉，并不是需要内存中必须要这么大的一块空间。
但是总的来说，归并排序不是原地排序，其需要额外的空间来实现其功能，这是使用归并排序时需要考虑的一个因素。 -
稳定性
关于这点，我们可以具体关注一下代码中的合并部分：
while (i <= half && j <= right) {
if (array[i] <= array[j]) { // stable
temp[t++] = array[i++];
} else {
temp[t++] = array[j++];
}
}
当两部分中出现相同数字时，我们是先将左边的数字进行了合并，并没有改变数字间的先后顺序，所以归并排序是稳定的排序算法。
-
数据规模
根据我们之前的分析，归并排序的时间复杂度是，并且值得注意的一点是无论数据规模、数据本身情况如何，它的时间复杂度稳定为
这些牺牲，在数据量很大的情况下，他们所占用时间的比例是比较小的，在能够直接减少计算次数的情况下，这些牺牲是值得的。
但是当数据量比较小的时候，这些操作所占的时间就不容忽视了，很有可能被插入排序等的算法给超过。
插入排序由于数据自身的优化，很可能在某一次排序之后数据已经有序，便可以直接返回。其最好情况时间复杂度为，而且插入排序是原地排序。
综合来看，归并排序的时间复杂度固然优秀，但是对于数据量较小的情况，其在内存空间等地方做的牺牲便有些得不偿失。在小数据量的情况下，由于其恒定的时间复杂度，反而可能被其他最好时间复杂度为
的排序算法给反超。
所以一句话，数据量大，需要稳定排序，空间不是很重要，请使用归并排序。
