一、什么是歸并排序

1、整體是遞歸，左邊排好序+右邊排好序+merge讓整體有序
2、讓其整體有序的過程里用了排外序方法
3、利用master公式來求解時間復雜度
4、當然可以用非遞歸實現(xiàn)

二、歸并排序說明

1、首先有一個f函數(shù)
void f(arr, L, R)
說明：在arr上，從L到R范圍上讓它變成有序的

2、遞歸調用

（1）先f(L, M)之間有序
（2）f(M+1, R)之間有序
（3）變成整體有序

左邊是2、3、5，右邊是0，5，6
準備一個一樣長的輔助空間，然后左指針指向2，右指針指向0，誰小拷貝誰
然后右邊的指針往后移，再次比較2和5，誰小拷貝誰，以此類推

（4）整體有序后，再把這一塊空間刷回去

三、代碼

package class03;public class Code01_MergeSort {/*** 變成整體有序* @param arr* @param L 數(shù)組下標* @param M 數(shù)組下標* @param R 數(shù)組下標*/public static void 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;while (p1 <= M && p2 <= R) {help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];}//要么p1越界了，要么p2越界了//看左邊小于等于Mwhile (p1 <= M) {help[i++] = arr[p1++];}//還是右邊小于等于Rwhile (p2 <= R) {help[i++] = arr[p2++];}for (i = 0; i < help.length; i++) {arr[L + i] = help[i];}}/*** 遞歸方法實現(xiàn)* arr[L...R]范圍上，變成有序* @param arr*/public static void mergeSort1(int[] arr) {if (arr == null || arr.length < 2) {return;}process(arr, 0, arr.length - 1);}public static void process(int[] arr, int L, int R) {if (L == R) { // base casereturn;}int mid = L + ((R - L) >> 1);process(arr, L, mid);process(arr, mid + 1, R);merge(arr, L, mid, R);}/*** 非遞歸方法實現(xiàn)* @param arr*/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) {int M = L + mergeSize - 1;if (M >= N) {break;}int R = Math.min(M + mergeSize, N - 1);merge(arr, L, M, R);L = R + 1;}if (mergeSize > N / 2) { //防止溢出break;}mergeSize <<= 1; //左移后賦值，相當于乘2后賦值}}public static void main(String[] args) {int[] aaa = {99, 100, 50, 70, 88, 10, 9, 35, 1, 98};int[] bbb = {99, 100, 50, 70, 88, 10, 9, 35, 1, 98};mergeSort1(aaa);for (int i: aaa) {System.out.print(i + " ");}System.out.println();mergeSort2(bbb);for (int i: bbb) {System.out.print(i + " ");}System.out.println();}
}

（1）遞歸說明

（2）非遞歸說明

原理：
k=2
相鄰兩個數(shù)之間merge在一起
k=4
四個數(shù)一組，merge在一起
...
一直到k到達N或者超過N

回到代碼，代碼中mergeSize就是k，外層while循環(huán)
? N ?10
? mergeSize ?1
? L ?0
? 內層while循環(huán)
? ? M ?0
? ? R ?1
? ? merge(arr, 0, 0, 1)
? ? L ?2
? ??
? ? M ?2
? ? R ?3
? ? merge(arr, 2, 2, 3)
? ? L ?4
? ??
? ? M ?4
? ? R ?5
? ? merge(arr, 4, 4, 5)
? ? L ?6
? ??
? ? ...

然后mergeSize變成2，變成4...

四、歸并排序復雜度

T(N)=2*T(N/2)+O(N^1)
根據(jù)master可知時間復雜度為O(N*logN)
merge過程需要輔助數(shù)組，所以額外空間復雜度為O(N)
歸并排序的實質是把比較行為變成了有序信息并傳遞，比O(N^2)的排序快