參考
Java排序算法(六)：歸并排序
數(shù)據(jù)結(jié)構(gòu)和算法(Golang實(shí)現(xiàn))(23)排序算法-歸并排序

假設(shè)初始序列含有n個(gè)元素蹋笼，我們可以把它看成是n個(gè)有序的子序列，每個(gè)子序列的長(zhǎng)度為1，然后兩兩合并绒北，得到n/2個(gè)長(zhǎng)度為2的有序子序列替蔬，再兩兩歸并... 如此重復(fù)艺晴，直至得到一個(gè)長(zhǎng)度為n的有序序列位置导坟，這種排序方法稱為2路歸并排序溃论。
如：無序數(shù)組序列{50, 10, 90, 30, 70, 40, 80, 60, 20}

Paste_Image.png

public class MergeSort {

    public static void main(String[] args) {
        int[] arr = {50, 10, 90, 30, 70, 40, 80, 60, 20};
        System.out.println("排序之前：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }

        // 歸并排序
        mergeSort(arr);

        System.out.println();
        System.out.println("排序之后：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    /**
     * 歸并排序
     */
    public static void mergeSort(int[] arr) {
        int[] tmpArr = new int[arr.length];
        mergeSort(arr, tmpArr, 0, arr.length - 1);
    } 

    private static void mergeSort(int[] arr, int[] tmpArr, int low, int high) {
        if (low < high) {
            // 將數(shù)組arr分為arr[0..mid]和arr[mid+1..high]
            int middle = (low + high) / 2;  
            
            // 遞歸將arr[low..mid]歸并為有序的tmpArr[low..mid]
            mergeSort(arr, tmpArr, low, middle); 
            
            // 遞歸將arr[mid+1..high]歸并為有序的tmpArr[mid+1..high]
            mergeSort(arr, tmpArr, middle + 1, high); 
            
            // 將arr[low..mid]和arr[mid+1..high]歸并到tmpArr[low..high]
            merge(arr, tmpArr, low, middle + 1, high); 
        }
    }

    // 將有序的arr[low..mid]和arr[mid+1..high]歸并為有序的tmpArr[low..high]
    private static void merge(int[] arr, int[] tmpArr, int lowPos, int highPos, int highEnd) {
        int lowEnd = highPos - 1; 
        int tmpPos = lowPos;
        int numElements = highEnd - lowPos + 1; 

        // 將arr中的記錄由小到大歸并入tmpArr
        while (lowPos <= lowEnd && highPos <= highEnd){
            if (arr[lowPos] <= arr[highPos]){
                tmpArr[tmpPos++] = arr[lowPos++];
            }else{
                tmpArr[tmpPos++] = arr[highPos++];
            }
        }
        
        // 將剩余的arr[low..mid]復(fù)制到tmpArr
        while (lowPos <= lowEnd){
            tmpArr[tmpPos++] = arr[lowPos++]; 
        }
        
        // 將剩余的arr[mid+1..high]復(fù)制到tmpArr
        while (highPos <= highEnd){
            tmpArr[tmpPos++] = arr[highPos++]; 
        }

        // Copy tmpArr back
        for (int i = 0; i < numElements; i++, highEnd--){
            arr[highEnd] = tmpArr[highEnd];
        }
    }

}

時(shí)間復(fù)雜度：O(nlogn)
次算法是經(jīng)典的分治策略滔金，它將問題分成一些小的問題然后遞歸求解色解，而治的階段則將分的階段解得的各答案修補(bǔ)在一起，分而治之是遞歸非常有效的用法鹦蠕。
歸并排序是唯一一個(gè)有穩(wěn)定性保證的高級(jí)排序算法冒签，某些時(shí)候，為了尋求大規(guī)模數(shù)據(jù)下排序前后钟病，相同元素位置不變萧恕，可以使用歸并排序。