# 歸并排序
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/)
適合用歸并排序模板套的題目：統計一個數左邊或右邊有多少個數據大或者小，都可以用歸并排序改。
