# 归并排序
1. 程序的整体结构是递归形式的，即先让左边数据排好序，再让右边数据排好序，最后通过merge让整体有序（合并两个有序数组的操作）。
2. 让整体有序的过程是利用了外排序。
3. 利用master公式来求解时间复杂度，T(n) = 2 \* (n/2) + O(n) ==> O(nlgn)。
辅助操作：合并两个有序的数组
~~~
// 合并两个有序数组
public static void merge(int[] arr, int L, int mid, int R) {
int[] help = new int[R - L + 1];
int i = 0;
int p1 = L;
int p2 = mid + 1;
while (p1 <= m && p2 <= R) {
help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= m) {
help[i++] = arr[p1++];
}
while (p2 <= R) {
help[i++] = arr[p2++];
}
for (int i = 0; i < help.length; i++) {
arr[L + i] = help[i];
}
}
~~~
归并排序主要有递归和非递归两种实现方式：
~~~
public static void mergeSort1(int[] arr) {
if (arr == null || arr.length < 2) {
return ;
}
process(arr, 0, arr.length - 1);
}
// arr[L...R]范围上变成有序的
// T(N) = 2 * T(N/2) + O(N)
public static void process(int[] arr, int L, int R) {
if (L == R) {
// base case
return ;
}
int mid = L + ((R - L) >> 1);
process(arr, L, mid);
process(arr, mid + 1, R);
merge(arr, L, mid, R);
}
~~~
**非递归实现**
~~~
public static void mergeSort2(int[] arr) {
if (arr == null || arr.length < 2) {
return ;
}
int N = arr.length;
// 左右一组的大小，当前有序的左组长度
int mergeSize = 1;
while (mergeSize < N) {
int L = 0;
while (L < N) {
// 这个while就是模拟递归的过程
int mid = L + mergeSize - 1;
if (mid >= N) {
// 只剩下左组的，肯定是有序的
break;
}
int R = Math.min(mid + mergeSize, N - 1);
merge(arr, L, mid, R);
L = R + 1;
}
if (mergeSize > N / 2) {
// 防止下面的mergeSize <<= 1的时候溢出了。导致最外面的循环判断错误
break;
}
// 每次都乘2
mergeSize <<= 1;
}
}
~~~
不管是递归方式，还是非递归方式，归并排序的时间复杂度为O(nlgn)。
> 面试题
>
> 在一个数组中，一个数左边比它小的数的总和，叫数的小和，所有数的小和累加起来，叫做数组小和；求一个nums数组的数组小和。
>
> 例如：\[1,3,4,2,5\]
>
> 1：没有
>
> 3: 1
>
> 4:1,3
>
> 2:1
>
> 5:1,3,4,2
>
> 总共：1+1+3+1+1+3+4+2 = 16
思路：
* 当在merge过程中左组比右组小时，统计总共有多少个小和。
* 当在merge过程中左组元素比右组元素大时，跳过。
* 相等的时候先拷贝右组（移动右组指针），不产生小和。
* 重复上面过程，直到左组或右组有一方溢出就不统计了。
code
~~~
public static int smallSum(int[] arr) {
if (arr == null || arr.length < 2) {
retur 0;
}
return process(arr, 0, arr.length - 1);
}
public static int process(int[] arr, int l, int r) {
if (l == r) {
return 0;
}
int mid = l + ((r - l) >> 1);
return process(arr, l, mid) + process(arr, mid + 1, r) + merge(arr, l, mid, r);
}
public static int merge(int[] arr, int l, int m, int r) {
int[] help = new int[r - l + 1];
int i = 0;
int p1 = L;
int p2 = m + 1;
int res = 0;
while (p1 <= m && p2 <= r) {
res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= m) {
help[i++] = arr[p1++];
}
while (p2 <= R) {
help[i++] = arr[p2++];
}
for (int i = 0; i < help.length; i++) {
arr[L + i] = help[i];
}
return res;
}
~~~
> 题目二：在数组中求所有的降序对
>
> [https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/](https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/)
适合用归并排序模板套的题目：统计一个数左边或右边有多少个数据大或者小，都可以用归并排序改。
