本文轉載自微信公眾號「貝塔學JAVA」，作者Silently9527 。轉載本文請聯系貝塔學JAVA公眾號。

前言

本篇我們談一種基于歸并操作完成排序的算法。

歸并排序算法思路

要將一個數組排序，可以先將數組分為兩個數組分別排序，然后再將結果歸并在一起，重復遞歸這個過程，直到數組整體有序，這就是歸并排序的算法思路。

歸并排序的優點是它能夠保證任意長度為N的數組排序所需的時間與 NlogN 成正比，這個優點是初級排序無法達到的。

缺點是因為歸并操作需要引入額外的數組，額外的空間與N成正比

原地歸并實現

在實現歸并排序之前，我們需要先完成兩個有序數組的歸并操作，即將兩個有序的數組合并成一個有序的數組；

• 在此過程中我們需要引入一個輔助數組；
• 定義的方法簽名為merge(a, lo, mid, hi)，這個方法將數組a[lo..mid]與a[mid..hi]歸并成一個有序的數組，結果存放到a[lo..mid]中；
• 該方法中需要使用的上一篇中的公共函數 less ，參考上一篇文章《常見的初級排序算法，這次全搞懂》

public class MergeSort implements SortTemplate { 
    private Comparable[] aux; 
 
    @Override 
    public void sort(Comparable[] array) { 
        //待實現 
    } 
 
    private void merge(Comparable[] a, int lo, int mid, int hi) { 
        for (int i = lo; i <= hi; i++) { 
            aux[i] = a[i]; 
        } 
        int i = lo, j = mid + 1; 
        for (int k = lo; k <= hi; k++) { 
            if (i > mid) { 
                a[k] = aux[j++]; 
            } else if (j > hi) { 
                a[k] = aux[i++]; 
            } else if (less(aux[i], aux[j])) { 
                a[k] = aux[i++]; 
            } else { 
                a[k] = aux[j++]; 
            } 
        } 
    } 
 
} 

自頂向下的歸并排序

基于分而治之的思想，大的數組排序，先遞歸拆分成小的數組，保證小的數組有序再歸并，直到整個數組有序，這個操作就是自頂向下的歸并排序

public class MergeSort implements SortTemplate { 
    private Comparable[] aux; 
 
    @Override 
    public void sort(Comparable[] array) { 
        aux = new Comparable[array.length]; 
        doSort(array, 0, array.length - 1); 
    } 
 
    private void doSort(Comparable[] array, int lo, int hi) { 
        if (lo >= hi) { 
            return; 
        } 
        int mid = (hi - lo) / 2 + lo; 
        doSort(array, lo, mid); 
        doSort(array, mid + 1, hi); 
        merge(array, lo, mid, hi); 
    } 
 
    private void merge(Comparable[] a, int lo, int mid, int hi) { 
        //省略 
    } 
 
} 

以上代碼是標準的遞歸歸并排序操作，但是經過仔細思考之后，該算法還有可以優化的地方

「測試數組是否已經有序」；如果a[mid]<=a[mid+1]，那么我們就可以跳過merge方法，減少merge操作；修復之后的doSort方法

private void doSort(Comparable[] array, int lo, int hi) { 
    if (lo >= hi) { 
        return; 
    } 
    int mid = (hi - lo) / 2 + lo; 
    doSort(array, lo, mid); 
    doSort(array, mid + 1, hi); 
    if (array[mid].compareTo(array[mid + 1]) >= 0) { 
        merge(array, lo, mid, hi); 
    } 
} 

「對于小規模的數組可以是用插入排序」；對于小規模的數組使用歸并排序會增加遞歸調用棧，所以我們可以考慮使用插入排序來處理子數組的排序

private void doSort(Comparable[] array, int lo, int hi) { 
    if (lo >= hi) { 
        return; 
    } 
 
    if (hi - lo < 5) { //測試，小于5就使用插入排序 
        insertionSort(array, lo, hi); 
        return; 
    } 
 
    int mid = (hi - lo) / 2 + lo; 
    doSort(array, lo, mid); 
    doSort(array, mid + 1, hi); 
    if (less(array[mid + 1], array[mid])) { 
        merge(array, lo, mid, hi); 
    } 
} 
 
//插入排序 
private void insertionSort(Comparable[] array, int lo, int hi) { 
    for (int i = lo; i <= hi; i++) { 
        for (int j = i; j > lo && less(array[j], array[j - 1]); j--) { 
            exch(array, j, j - 1); 
        } 
    } 
} 

「節省復制元素到輔助數組的時間」；要實現該操作較麻煩，需要在每一層遞歸的時候交換輸入數據和輸出數組的角色；修改之后的完整代碼如下：

public class MergeSort implements SortTemplate { 
    private Comparable[] aux; 
 
    @Override 
    public void sort(Comparable[] array) { 
        aux = array.clone(); 
        doSort(aux, array, 0, array.length - 1); 
    } 
 
    private void doSort(Comparable[] src, Comparable[] dest, int lo, int hi) { 
        if (lo >= hi) { 
            return; 
        } 
 
        if (hi - lo < 5) { //測試，小于5就使用插入排序 
            insertionSort(dest, lo, hi); 
            return; 
        } 
 
        int mid = (hi - lo) / 2 + lo; 
        doSort(dest, src, lo, mid); 
        doSort(dest, src, mid + 1, hi); 
        if (less(src[mid + 1], src[mid])) { 
            merge(src, dest, lo, mid, hi); 
        } 
    } 
 
    //插入排序 
    private void insertionSort(Comparable[] array, int lo, int hi) { 
        for (int i = lo; i <= hi; i++) { 
            for (int j = i; j > lo && less(array[j], array[j - 1]); j--) { 
                exch(array, j, j - 1); 
            } 
        } 
    } 
 
    private void merge(Comparable[] src, Comparable[] dest, int lo, int mid, int hi) { 
        int i = lo, j = mid + 1; 
        for (int k = lo; k <= hi; k++) { 
            if (i > mid) { 
                dest[k] = src[j++]; 
            } else if (j > hi) { 
                dest[k] = src[i++]; 
            } else if (less(src[i], src[j])) { 
                dest[k] = src[i++]; 
            } else { 
                dest[k] = src[j++]; 
            } 
        } 
    } 
 
} 

每一層遞歸操作都會讓子數組有序，但是子數組可能是aux[lo..hi]也有可能是a[lo..hi]；由于第一次調用doSort傳入的是src=aux，dest=array，所以遞歸最后的結果一定是輸入到了array中，保證了array整體排序完成

自底向上的歸并排序

實現歸并算法還有另一種思路，就是先歸并哪些小的數組，然后再成對歸并得到子數組，直到整個數組有序

public class MergeSort implements SortTemplate { 
    private Comparable[] aux; 
 
    @Override 
    public void sort(Comparable[] array) { 
        int length = array.length; 
        aux = new Comparable[length]; 
        for (int sz = 1; sz < length; sz += sz) { 
            for (int i = 0; i < length - sz; i += 2 * sz) { 
                merge(array, i, i + sz - 1, Math.min(i + 2 * sz - 1, length - 1)); 
            } 
        } 
    } 
 
    private void merge(Comparable[] a, int lo, int mid, int hi) { 
        for (int i = lo; i <= hi; i++) { 
            aux[i] = a[i]; 
        } 
        int i = lo, j = mid + 1; 
        for (int k = lo; k <= hi; k++) { 
            if (i > mid) { 
                a[k] = aux[j++]; 
            } else if (j > hi) { 
                a[k] = aux[i++]; 
            } else if (less(aux[i], aux[j])) { 
                a[k] = aux[i++]; 
            } else { 
                a[k] = aux[j++]; 
            } 
        } 
    } 
 
}