『归并排序』基于分支算法实现，时间复杂度为：O(nlogn)。一般有两种实现方式，一种是自顶向下的递归实现，但递归调用需要使用额外的栈空间，空间复杂度为 O(logn)；另一种是自底向上的时间方式，空间复杂度为常数级的 O(1)。
nlogn 比 n^2 快多少？
下面的表格中简单比较了在 10 ～ 10^5 数据量下，nlogn 和 n^2 分别耗费的时间：
| n^2 | nlogn | faster | |
|---|---|---|---|
| n = 10 | 100 | 33 | 3 |
| n = 100 | 1000 | 664 | 15 |
| n = 10^3 | 10^6 | 9966 | 100 |
| n = 10^4 | 10^8 | 132877 | 753 |
| n = 10^5 | 10^10 | 1660964 | 6020 |
最后一列 faster 表示了 nlogn 比 n^2 快了多少倍。在 n = 10 时，nlogn 只比 n^2 快了 3 倍，在现代的计算机上，可能只是 1ms 和 3ms 的差别，我们可能根本感知不到。
但随着 n 的数据量逐渐增大，nlogn 比 n^2 的优势会越来越大，当 n = 10^5 时，这个数据量还没那么大的时候，nlogn 已经比 n^2 快了近 6000 倍。这是什么概念呢？如果我们处理一个 10^5 左右数据量的数据集，用 nlogn 的算法处理需要花费一天，那么用 n^2 的算法就需要花费六千天。
实现思路 - 自顶向下
现有一待排序数组 [8,6,2,3,1,5,7,4]。归并排序要做的事就是将该数组分成两半，然后分别将左边数组排序，再将右边数组排序，之后再将两部分归并起来：
对左边和右边数组排序的过程，就是再将左边的数组和右边的数组分成两半，然后对每个部分排序：
对于上面数组的每个部分进行的排序操作，依然是先将其分半，之后再将其归并。等到数组不能再分的时候，也就是下图中的这种情况，每个元素就是单独的一半时，每个元素默认就是有序的了：
上述待排序的数组共 8 个元素，每次将每个整块元素分为两块，共分了 3 次，也就是计算 8 除以 2 除几次等于 1，换算成数学公式就是以 2 为底的 8 的对数 等于 3:
如果共有 N 个元素的话，就会分成 logN 个层级，如果 N 为奇数的话，向上取整就好了。
===》 归并的过程：
虽然每层都将元素分成了不同的部分，但每层要处理的元素个数是相同的。如果每层都能以 O(N) 的时间复杂度解决的话，那么就设计出了 Nlog(N) 级别的算法。
实际上，这也是 Nlog(N) 时间复杂度算法的主要来源。通常都是上述这种二分法达到了 log(N) 的层级，之后每个层级用 O(N) 级别的算法做事情。
大概流程如下：
对第三层中的每一半进行两两归并，结果如下↯↯
对第二层中的每一半进行两两归并，结果如下↯↯
🤔 现在需要解决的问题是，我们能不能将数组划分成两部分，之后将这两部分都分别排好序后，使用 O(N) 级别的算法，将它们归并到一起，形成一个新的数组呢？
答案是可以的。但是在原数组上操作比较困难，需要开辟一块新的空间。这也是归并排序与其他排序不同的地方。归并排序虽然能将算法的时间复杂度提升到 O(nlogn) 级别，但是它比其他的算法要多使用了额外的空间。
归并的过程简单描述如下：
使用索引 k 指向原数组，索引 i 指向辅助数组的左半部分的第一个元素，索引 j 指向辅助数组的右半部分的第一个元素：
比较 索引i 和 索引j 指向的元素的值，如果 nums[i] > nums[j]，就将 nums[j] 的值赋给 索引k 指向的值，并将 索引j 和 索引k 移动到下一个元素：
重复上述操作：
为了避免 i 和 j 越界，需要设置 l、r 和 mid 指针分别指向如下位置：
码一下
Java 版
public class MergeSort {
public static void sort(int[] nums) {
mergeSort(nums, 0, nums.length - 1);
}
/**
* 递归使用归并排序，对 arr[l...r] 的范围进行排序
*
* @param nums
* @param l
* @param r
*/
private static void mergeSort(int[] nums, int l, int r) {
// 处理递归到底的情况
if (l >= r) {
return;
}
int mid = l + (r - l) / 2;
mergeSort(nums, l, mid);
mergeSort(nums, mid + 1, r);
merge(nums, l, mid, r);
}
/**
* 对 arr[l...mid] 和 arr[mid+1...r] 两部分进行合并
*
* @param nums
* @param l
* @param mid
* @param r
*/
private static void merge(int[] nums, int l, int mid, int r) {
// 辅助的空间，aux -> auxiliary
int[] aux = new int[r - l + 1];
// 初始化辅助空间的值，aux 数组从索引 0 开始赋值，但 nums 数组从 l 开始遍历，所以赋值时需要设置 i-l 的偏移量
for (int i = l; i <= r; i++) {
aux[i - l] = nums[i];
}
// 索引 i 和 j 分别指向 mid 指针左右两侧的首个元素
int i = l, j = mid + 1;
for (int k = l; k <= r; k++) {
if (i > mid) {
nums[k] = aux[j - l];
j++;
} else if (j > r) {
nums[k] = aux[i - l];
i++;
} else if (aux[i - l] < aux[j - l]) {
nums[k] = aux[i - l];
i++;
} else {
nums[k] = aux[j - l];
j++;
}
}
}
}GoLang 版
优化
优化一
在合并两部分数组之前，就已经保证了这两部分数组，从 l ~ mid，mid+1 ~ r 都是有序的，那么如果 nums[mid] <= nums[mid+1]，就无需在执行合并两部分数组的操作了，因为这两部分已经是有序的了。所以只有当 nums[mid] > nums[mid+1] 时，才需要执行 merge 操作。修改如下：
public class MergeSortOptimizeOne {
public static void sort(int[] nums) {
mergeSort(nums, 0, nums.length - 1);
}
private static void mergeSort(int[] nums, int l, int r) {
if (l >= r) {
return;
}
int mid = l + (r - l) / 2;
mergeSort(nums, l, mid);
mergeSort(nums, mid + 1, r);
if (nums[mid] > nums[mid + 1]) {
merge(nums, l, mid, r);
}
}
private static void merge(int[] nums, int l, int mid, int r) {
int[] aux = new int[r - l + 1];
for (int i = l; i <= r; i++) {
aux[i - l] = nums[i];
}
int i = l, j = mid + 1;
for (int k = l; k <= r; k++) {
if (i > mid) {
nums[k] = aux[j - l];
j++;
} else if (j > r) {
nums[k] = aux[i - l];
i++;
} else if (aux[i - l] < aux[j - l]) {
nums[k] = aux[i - l];
i++;
} else {
nums[k] = aux[j - l];
j++;
}
}
}
}优化二
当数组内待排序的元素个数比较小时，整个数组近乎有序的概率就比较大，此时可以将归并排序替换为插入排序，因为在近乎有序的情况下，插入排序更有优势。
实现思路 - 自底向上
现在有一待排序数组：[8,6,2,3,1,5,7,4]，从左到右将该数组中的元素依次划分成小段，比如两个元素一个小段：
进行归并排序：
当归并元素排序完成一轮之后，再 4 个元素一个小段的进行归并排序：
最后再 8 个元素一个小段，在当前示例中也就是整个数组全体，进行归并排序：
最终完成了整个数组的排序过程。
