歸并排序主要是兩大模塊 分治 和 合并??

即將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并?由于使用了新的數組 那么空間復雜度就為O(n) 但這一排序會相同數據的位置保持不變即 保持數組的穩定性?

以[8, 4, 5, 7, 1, 3, 6, 2]為例

執行的順序為

mergeSort(A, 0, 7) ?// 處理整個數組

├── mergeSort(A, 0, 3) ?// 處理左半部分

│ ??├── mergeSort(A, 0, 1) ?// 處理 [8, 4]

│ ??│ ??├── mergeSort(A, 0, 0) ?// 處理 [8]（終止）

│ ??│ ??├── mergeSort(A, 1, 1) ?// 處理 [4]（終止）

│ ??│ ??├──? merge(A, 0, 1, temp) ?// 合并 [8] 和 [4]

│ ??├── mergeSort(A, 2, 3) ?// 處理 [5, 7]

│ ??│ ??├── mergeSort(A, 2, 2) ?// 處理 [5]（終止）

│ ??│ ??├── mergeSort(A, 3, 3) ?// 處理 [7]（終止）

│ ??│ ??├──? merge(A, 2, 3, temp) ?// 合并 [5] 和 [7]

│ ??├──? merge(A, 0, 3, temp) ?// 合并 [4, 8] 和 [5, 7]

├── mergeSort(A, 4, 7) ?// 處理右半部分

│ ??├── mergeSort(A, 4, 5) ?// 處理 [1, 3]

│ ??│ ??├── mergeSort(A, 4, 4) ?// 處理 [1]（終止）

│ ??│ ??├── mergeSort(A, 5, 5) ?// 處理 [3]（終止）

│ ??│ ??├── merge(A, 4, 5, temp) ?// 合并 [1] 和 [3]

│ ??├── mergeSort(A, 6, 7) ?// 處理 [6, 2]

│ ??│ ??├── mergeSort(A, 6, 6) ?// 處理 [6]（終止）

│ ??│ ??├── mergeSort(A, 7, 7) ?// 處理 [2]（終止）

│ ??│ ??├── merge(A, 6, 7, temp) ?// 合并 [6] 和 [2]

│ ??├── ?merge(A, 4, 7, temp) ?// 合并 [1, 3] 和 [2, 6]

├── ?merge(A, 0, 7, temp) ?// 合并 [4, 5, 7, 8] 和 [1, 2, 3, 6]

關鍵點在于

?mergeSort()?先遞歸拆分，直到 start == end（單個元素），然后回溯時合并。

merge()?只在兩個子數組都已經排序后才會執行。

merge()?總是在 mergeSort()?遞歸調用之后執行，保證子數組是有序的再進行合并

類似于二叉樹的后續遍歷 即左右根

??????????[8, 4, 5, 7, 1, 3, 6, 2]

??????????/ ??????????????????????\

??[8, 4, 5, 7] ??????????????????[1, 3, 6, 2]

?????/ ????????\ ??????????????????/ ????????\

??[8, 4] ????[5, 7] ????????????[1, 3] ????[6, 2]

???/ ???\ ????/ ???\ ???????????/ ???\ ?????/ ???\

?[8] ???[4] [5] ???[7] ???????[1] ???[3] ?[6] ???[2]

下面為實現的代碼

public class Solution {

? ? public void sortIntegers2(int[] A) {

? ? ? ?if(A==null||A.length<=0)

? ? ? ?{

? ? ? ? ? ?return;

? ? ? ?}

? ? ? ?int[] temp=new int[A.length];

? ? ? ?mergeSort(A,0,A.length-1,temp);

? ? }

? ? void mergeSort(int[] A,int start,int end,int[] temp)

? ? {

? ? ? ? if(start>=end)

? ? ? ? {

? ? ? ? ? ? return;

? ? ? ? }

? ? ? ? int mid=(start+end)/2;

? ? ? ? //遞歸將其分治 將所有的數字最終分解為一個元素

? ? ? ? mergeSort(A,start,mid,temp);

? ? ? ? mergeSort(A,mid+1,end,temp);

? ? ? //遞歸完成后進行合并已排好序的數組?

? ? ? ? merge(A,start,end,temp);

? ? }

? ? void merge(int[] A,int start,int end,int[] temp)

? ? {

? ? ? ? int middle = (start + end) / 2;

? ? ? ? int leftIndex=start;

? ? ? ? int rightIndex=middle+1;

? ? ? ? int Index=start;

? ? ? ? //比較兩個左右子數列 按照從小打大的順序進行排序

? ? ? ? while(leftIndex<=middle&&rightIndex<=end)

? ? ? ? {

? ? ? ? ? ? if(A[leftIndex]<=A[rightIndex])

? ? ? ? ? ? {

? ? ? ? ? ? ? ? temp[Index++]=A[leftIndex++];

? ? ? ? ? ? }else

? ? ? ? ? ? {

? ? ? ? ? ? ? ? temp[Index++]=A[rightIndex++];

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? //將余下的左子序列賦值至剩余的temp數組中

? ? ? ? while(leftIndex<=middle)

? ? ? ? {

? ? ? ? temp[Index++]=A[leftIndex++];

? ? ? ? }

? ? ? ? //將余下的右子序列賦值至剩余的temp數組中

? ? ? ? while(rightIndex<=end)

? ? ? ? {

? ? ? ? temp[Index++]=A[rightIndex++];

? ? ? ? }

? ? ? ? for(int i=start;i<=end;i++)

? ? ? ? {

? ? ? ? ? ? A[i]=temp[i];

? ? ? ? }

? ? }

? ? }