1. 歸并排序原理

? ? ? ? 歸并排序（MERARE-SORT）簡單來說就是將大的序列先視為若干個比較小的數組，分成比較小的結構，然后是利用歸并的思想實現的排序方法，該算法采用經典的分治策略（分就是將問題分成一些小的問題分別求解，而治則將分的階段得到的各答案“合”在一起）。

????????歸并排序算法就是應用歸并思想的一個典型例子。在歸并排序中，我們首先將未排序的數組不斷地劃分成兩個子數組，直到子數組的長度為1。然后，我們合并子數組，使得子數組按照排序規則排列，最后得到排序完成的數組。

????????分治法可以看作是"分而治之"的意思，也就是把一個復雜的問題分成兩個或更多的相同或相似的子問題，直到最后子問題可以簡單的直接求解，從而使得原問題的解即子問題的解的合并。

都需要遞歸地解決子問題，并在最后合并子問題的解。

1. 上圖就是將 一個大的數組二分成一個個小的數組，知道最后每個劃分的數組只有一個元素的時候，開始進行合并，這種操作就是分階段，可以理解為遞歸拆分子序列的過程，遞歸的深度為logn。
2. 治階段，將兩個已經有序的子序列合并成一個有序序列。

遍歷時處理元素的過程：

?總結歸并排序的思路：

• 首先將原數組二分的拆分，直到最后問題變成最小的時候，也就是每個子數組只有一個元素，開始進行第二步。
• 將兩個子數組合并，按照合并兩個有序數組的方式進行，按照圖中每個左右子樹從下往上，然后再將左右子樹合并，每個子樹最后都是一個有序數組。

    public static void mergeSort(int[] array, int start, int end, int temp[]){if (start >= end){return;}mergeSort(array, start, (start + end) / 2,temp);mergeSort(array, (start + end) / 2 + 1, end,temp);merge(array, start, end, temp);}public static void merge(int[] array, int start, int end, int[] temp){int middle = (start + end) /2;int left = start;int right = middle + 1;int index = left;//將兩邊的最小元素移到左邊while (left <= middle && right <= end){if (array[left] < array[right]){temp[index++] = array[left++];}else {temp[index++] = array[right++];}}//左端元素遍歷完，依次把右端元素轉移過來while (left <= middle){temp[index++] = array[left++];}//左端元素遍歷完，依次把右端元素轉移過來while (right <= end){temp[index++] = array[right++];}//將temp中的元素依次轉到array中，for (int i = start; i <= end; i++){array[i] = temp[i];}}