摘要
归并排序就是将序列不断向下拆分成最小的序列（只有两个元素），然后从这个地方开始排序，然后向上合并成新的序列和排序，直到合并为一个序列（这时，这个序列就是有序的）
代码实现上用了递归的思路处理，归并排序在时间复杂度上比前3种有优势，具体可以用到什么样的场景，暂时没有想到，就先学习下逻辑，增长见识。
逻辑
归并排序多少有些空间换取时间的思想，所以代码实现中会创建一个临时的序列。具体的逻辑如下：
- 将序列不断平均分成两个子序列，直到各子序列中只有一个元素
- 不断合并子序列为有序序列，直到成为一个序列为止
实现
创建一个长度是序列一半长度的临时序列，用于序列的合并。
leftArray = (E[])new Comparable[array.length >> 1];
sort(0, array.length);
这里是递归的思想，将序列不断拆分到最小单位（只有两个元素）。这个递归稍微一些难理解它的执行顺序，这里特别梳理一下。
递归思路：
方法中存在递归代码时，当代码执行到递归方法处，会直接执行递归方法，直到满足结束条件时，会一层层返回，并执行递归方法之后的代码块。这里也就可以推断出，凡是使用递归方法，必须要有一个终止递归的条件，否则递归方法会进入死循环。
大致的执行循序是通过递归一直拆分，直到元素小于等于2个的时候，就向上返回，并执行 merge 方法来合并序列。
/*
* 对 [begin, end) 范围的数据进行归并排序
*
*/
private void sort(int begin, int end) {
if (end - begin < 2) return;
int mid = (begin + end) >> 1;
sort(begin, mid);
sort(mid, end);
merge(begin, mid, end);
}
合并排序有两点比较有意思的处理：
- 看 while 循环时，为什么只判断
li<le，不用判断右侧？因为左侧是临时序列，这里要将有序的元素依次放入array中，所以只需要考虑两种极端情况，临时序列都比右侧小，那么临时序列元素放进去后，右侧序列是不需要动的。右侧序列都比临时序列小，那么就会整体把右侧序列往前放，放完之后是不会结束 while 循环，会继续将临时序列放进去，直到临时序列元素放完。 - 这里看
array一直只有一个，所以这个序列中的部分位置有序也是在array上操作，为了达到这个效果，就用begin和end来获得到在序列中的真实位置。这样的处理好处就是不用额外创建空间来处理。
在排序的时候有一个疑问，难道不会有左侧序列或者右侧序列本就不是有序的吗？
答案肯定是不会。因为递归思想来看，当执行完合并排序，才会向上执行，在上层再执行合并排序时，这个序列已经在下层排序完成了。
private void merge(int begin, int mid, int end) {
int li = 0, le = mid - begin;
int ri = mid, re = end;
int ai = begin;
// 备份左边数组
for (int i = li; i < le; i++) {
leftArray[i] = array[begin + i];
}
// 如果左边没有结束
while (li < le) {
if (ri < re && cmp(array[ri], leftArray[li]) < 0) { // 增加稳定性
array[ai++] = array[ri++];
} else {
array[ai++] = leftArray[li++];
}
}
}
代码中的合并思路，可以用到合并两个有序序列的场景中，是一个非常好的思想。
时间和空间复杂度
- 最坏、平均时间复杂度：O(nlogn)
- 最好时间复杂度：O(nlogn)
- 空间复杂度：O(n)
- 属于稳定排序