將一組數(shù)據(jù)先進行分組，取index中間值。直到每組只剩下一個數(shù)字。
之后按順序(從小到大)合并。
采用遞歸進行分。

完整代碼見文末

分組函數(shù)

public static void MergeSort(int[] arr, int L, int R)

排序函數(shù)

public static void merge(int[] arr, int L, int R, int mid)

分組

例子：
Arr={10, 3, 8, 4}
這組數(shù)據(jù)使用歸并排序。
Value： 10， 3， 8，4
Index： 0， 1， 2，3

開始分組
L = 0; R=3;
將四個數(shù)字分組
獲取中間值 mid = (L + R) / 2 = 1
那么已經(jīng)分為了兩組
0 - mid,
mid + 1 - R

即每次分組需確認的是mid值

int mid = (L + R) / 2;

左邊：
Value：10， 3
Index： 0， 1
右邊：
Value：8，4
Index：2，3

左邊再分：
L = 0, R = 1； mid = 0
左：
Value：10
Index: 0
右：
Value：3
Index：1

右側同理。
將一組數(shù)分到每組一個數(shù)據(jù)需要重復取mid值
即

        int mid = (L + R) / 2;
        MergeSort(arr, L, mid);
        MergeSort(arr, mid + 1, R);

每次分組都先要保證L和R不再

已經(jīng)分到一個數(shù)據(jù)一組，開始合并。

最先進行合并的是 10 和 3

合并

合并的方法及參數(shù)為

public static void merge(int[] arr, int L, int R, int mid)

創(chuàng)建一個temp[]來根據(jù)大小存放合并的兩組數(shù)。

        int l = L;//分組1的索引
        int m = mid + 1;//分組2的索引
        int[] temp = new int[arr.length];
        int tempInd = l;

遍歷比較兩組數(shù)，根據(jù)順序存放進temp[]

 while (l <= mid && m <= R){
            if (arr[l] < arr[m])
                temp[tempInd++] = arr[l++];
            else
                temp[tempInd++] = arr[m++];
        }

將未存放進temp[]的數(shù)組1或數(shù)組2中的數(shù)據(jù)，進行處理。

        while (l <= mid)
            temp[tempInd++] = arr[l++];

        while(m <= R)
            temp[tempInd++] = arr[m++];

最后根據(jù)temp[]中的數(shù)據(jù)修改array[]，索引即為L和R

for (int i = L; i <= R; i++)
            arr[i] = temp[i];

完整代碼

public static void merge(int[] arr, int L, int R, int mid){
//        從小到大
        int l = L;
        int m = mid + 1;
        int[] temp = new int[arr.length];
        int tempInd = l;
        while (l <= mid && m <= R){
            if (arr[l] < arr[m])
                temp[tempInd++] = arr[l++];
            else
                temp[tempInd++] = arr[m++];
        }
        while (l <= mid)
            temp[tempInd++] = arr[l++];

        while(m <= R)
            temp[tempInd++] = arr[m++];

        for (int i = L; i <= R; i++)
            arr[i] = temp[i];

        System.out.println(Arrays.toString(temp));
    }

    public static void MergeSort(int[] arr, int L, int R){
        if (L == R)
            return;

        int mid = (L + R) / 2;
        MergeSort(arr, L, mid);
        MergeSort(arr, mid + 1, R);
        merge(arr, L, R, mid);
    }