1. 概述
我们总是可以将一个数组一分为二，然后二分为四，直到每一组只有两个元素，这可以理解为个递归的过程，然后将两个元素进行排序，之后再将两个元素为一组进行排序。直到所有的元素都排序完成。
image
2. 归并算法的思想
- 归并算法其实可以分为递归法和迭代法（自低向上归并）
- 两种实现对于最小集合的归并操作思想是一样的区别在于如何划分数组
先介绍下算法最基本的操作：
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
- 重复步骤3直到某一指针到达序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
- 假设我们现在在对一个数组的 arr[l...r] 部分进行归并，按照上述归并思想我们可将数组分为两部分 假设为 arr[l...mid] 和 arr[mid+1...r]两部分，注意这两部分可能长度并不相同，因为基数个数的数组划分的时候总是能得到一个 长度为1 和长度为2 的部分进行归并.
3 归并排序的 Java 实现：
有两种方法，一种是递归划分法，一种是迭代遍历法（自低向上）
3.1 递归划分法
/**
* @param arr 待排序数组
* @param left 其实元素角标 0
* @param right 最后一个元素角标 n -1
*/
private static void mergeSort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
//开始归并排序 向下取整
int mid = (left + right) / 2;
//递归划分数组
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
//检查是否上一步归并完的数组是否有序，如果有序则直接进行下一次归并
if (arr[mid] <= arr[mid + 1]) {
return;
}
//将两边的元素归并排序
merge(arr, left, mid, right);
}
/**
* arr[l,mid] 和 arr[mid+1,r] 两部分进行归并
*/
private static void merge(int[] arr, int left, int mid, int right) {
// 复制等待归并数组 用来进行比较操作，最将原来的 arr 每个角标赋值为正确的元素
int[] aux = new int[right - left + 1];
for (int i = left; i <= right; i++) {
aux[i - left] = arr[i];
}
int i = left;
int j = mid + 1;
for (int k = left; k <= right; k++) {
if (i > mid) {
//说明左边部分已经全都放进数组了
arr[k] = aux[j - left];
j++;
} else if (j > right) {
//说明左边部分已经全都放进数组了
arr[k] = aux[i - left];
i++;
} else if (aux[i - left] < aux[j - left]) {
//当左半个数组的元素值小于右边数组元素值得时候 赋值为左边的元素值
arr[k] = aux[i - left];
i++;
} else {
//当左半个数组的元素值大于等于右边数组元素值得时候 赋值为左边的元素值 这样也保证了排序的稳定性
arr[k] = aux[j - left];
j++;
}
}
}
3.2 迭代遍历法
迭代的时候我们是将数组分为 一个一个的元素，然后每两个归并一次，第二次我们将数组每两个分一组，两个两个的归并，直到分组大小等于待归并数组长度为止，即先局部排序，逐步扩大到全局排序
/**
* 自低向上的归并排序
*
* @param n 为数组长度
* @param arr 数组
*/
public static void mergeSortBU(int[] arr, int n) {
//sz = 2 : [0,1] [2.3] ...
//sz = 4 : [0..3] [4...7] ...
//sz 分组的大小
//因为merge的时候总是左右交换 所以这里size的大小是2的倍数
for (int sz = 2; sz <= 2 * n; sz = sz * 2) {
for (int i = 0; i + sz / 2 < n; i += sz) {//这里i += sz 是转移到下一个组里
//i + sz / 2 - 1 ：组里是右半段的起点
//Math.min(i + sz - 1, n - 1) 找到这组的最右边的索引
merge(arr, i, i + sz / 2 - 1, Math.min(i + sz - 1, n - 1));
}
}
}
4 归并排序的时间复杂度和空间复杂度分析
- 其实对于归并排序的时间复杂对有一个递归公式来推断出时间复杂度，但简单来讲假设数组长度为 N ，那么我们就有 logN 次划分区间，而最终会划分为常数 级别的归并，将所有层的归并时间加起来得到了一个 NlogN。
- 对于空间复杂度，我们通过算法实现可以看出我们归并过程申请了 长度为 N 的临时数组，来进行归并所以空间复杂度为 O(n);
** 归并排序总结：**
- 归并排序的算法时间平均复杂度为O(nlog(n))。
- 归并排序空间复杂度为 O(n)。
- 归并排序为稳定排序。
