歸併排序的原理
歸併排序是利用歸併的思想實現的排序方法，該方法採用經典的分治策略（分治法將問題分成一些小的問題然後遞歸求解，而治的階段則是將分的階段得到的答案修補在一起，即分而治之）。
圖解歸併排序
下面我們以待排序數組 8,4,5,7,1,3,6,2,9,10為例，以圖解的方式講解歸併排序的原理。
（1）分治原理圖（由於圖片太大，沒法截全，我進行了一定壓縮，所以看起來有點奇怪...）
從圖中可以看出，歸併排序是先將數組進行拆分，拆分到剩餘一個關鍵字，這是一個從大到小的過程。然後再進行治理，治理的過程也就是進行合併的過程，合併時會保證左右兩邊的數組內部各自有序。然後將兩個有序的數組合併到一個數組中，且合併後的數組有序。總結就是：遞歸拆分，回溯合併，合併時左右兩個數組內部有序。
（2）遞歸原理圖
在看遞歸原理圖前，我們先看下歸併排序的代碼，如下所示
1 public class MergeSort {
2 private static int count = 1;
3 public static void main(String[] args) {
4 int[] arr = {8, 4, 5, 7, 1, 3, 6, 2, 9, 10};
5 int[] temp = new int[arr.length];
6 split(arr, 0, arr.length - 1, temp);
7 System.out.println(Arrays.toString(arr));
8 }
9
10 /**
11 * 遞歸拆分數組然後合併
12 *
13 * @param arr 待拆分數組
14 * @param left 數組左邊下標
15 * @param right 數組右下標
16 * @param temp 用於存放合併後的有序序列的數組
17 */
18 public static void split(int[] arr, int left, int right, int[] temp) {
19 if (left >= right) {
20 return;
21 }
22 System.out.println("拆分第"+(count++)+"次");
23 int mid = left + (right - left) / 2;
24 //向左拆分
25 split(arr, left, mid, temp);
26 //向右拆分
27 split(arr, mid + 1, right, temp);
28 //每次拆分後都執行合併
29 merge(arr, left, mid, right, temp);
30 }
31
32 /**
33 * 合併兩個各自有序序列(以mid為界)
34 *
35 * @param arr 原始數組
36 * @param left 數組左邊下標
37 * @param mid 數組中間下標
38 * @param right 數組右邊下標
39 * @param temp 用於存放新的有序數組
40 */
41 public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
42 int i = left;
43 int j = mid + 1;
44 //temp中的原始下標
45 int t = 0;
46
47 while (i <= mid && j <= right) {
48 //兩邊數組都沒有比較完 繼續
49 if (arr[i] < arr[j]) {
50 //左邊數組中值更小
51 temp[t] = arr[i];
52 i++;
53 } else {
54 //右邊數組中值更小
55 temp[t] = arr[j];
56 j++;
57 }
58 t++;
59 }
60 //有一邊已經全部複製到temp中了
61 if (i <= mid) {
62 //左邊還沒有複製完，將左邊全部元素複製到temp中
63 while (i <= mid) {
64 temp[t] = arr[i];
65 i++;
66 t++;
67 }
68 } else if (j <= right) {
69 //右邊還沒有複製完，將右邊全部元素複製到temp中
70 while (j <= right) {
71 temp[t] = arr[j];
72 j++;
73 t++;
74 }
75 }
76 //將temp複製到原arr中
77 t = 0;
78 while (left <= right) {
79 arr[left] = temp[t];
80 left++;
81 t++;
82 }
83 }
84 }
我們都知道在jvm內存模型中，線程每調用一個方法就會將該方法壓入本線程的棧中。在遞歸方法的調用過程中也是如此，只不過每次壓棧的方法名都相同，這裡我們為了好區分遞歸執行到哪一層，人為的為遞歸方法編號，即每遞歸一次編號加1。如上圖所示，數組8,4,5,7,1,3,6,2,9,10第一次拆分時,left = 0,right=9,mid=4 (三者均表示下標)，然後繼續向左遞歸拆分即split1方法入棧，此時left=0,right=4,mid=2。然後繼續向左遞歸拆分。。。。直到left=right即只剩下一個數字無法再拆分，即我們上圖中的split4，所以split4方法出棧回溯到方法split3中，split3代碼向下執行，執行向右遞歸拆分，這裡我們為了方便區分，將向右遞歸的過程又畫了一個棧來表示，即上圖中間的棧圖，此時向右遞歸的split0入棧，此時left=right=1,split0齣棧，split3繼續向下執行，即執行merge合併方法，此時合併方法參數left=0,right=1,mid=0，即8和4兩個分別有序的數組進行合併(單個數字內部當然有序)。
merge方法執行完後，split3遞歸方法執行完畢，出棧，回溯到遞歸方法split2中，繼續執行上述步驟。需要說明的是，上述過程在向右遞歸時由於mid後面只有一個數字4，所以left=right=1，所以向右遞歸方法直接出棧，而在向左遞歸執行到split1時，mid後面有兩個數字7,1所以在向右遞歸時會將當前數組（7，1）繼續執行向左向右拆分，以保證數組與其他數組進行合併前內部有序。
（3）合併圖解
下面以最後一次合併為例，圖解合併的執行過程。即1,4,5,7,8與2,3,6,9,10兩個有序數組的合併過程
（4）總結
以上就是歸併排序的執行原理，主要分為以下步驟：
1.遞歸的方式進行拆分，將大的數組拆分成小的數組，直到剩餘一個不能拆分
2.回溯的時候進行合併，合併時以mid為界，左右兩邊各自有序，通過額外的空間temp數組，將兩個有序數組合併到一個有序數組中
3.將合併後的數組複製到原數組中，當回溯完成時整個數組有序