分類 -------------- 內(nèi)部比較排序
數(shù)據(jù)結(jié)構(gòu) ---------- 數(shù)組
最差時間復(fù)雜度 ---- O(nlogn)
最優(yōu)時間復(fù)雜度 ---- O(nlogn)
平均時間復(fù)雜度 ---- O(nlogn)
所需輔助空間 ------ O(n)
穩(wěn)定性 ------------ 穩(wěn)定

原理

???????歸并排序的實現(xiàn)分為遞歸實現(xiàn)與非遞歸(迭代)實現(xiàn)。遞歸實現(xiàn)的歸并排序是算法設(shè)計中分治策略的典型應(yīng)用，我們將一個大問題分割成小問題分別解決，然后用所有小問題的答案來解決整個大問題。非遞歸(迭代)實現(xiàn)的歸并排序首先進(jìn)行是兩兩歸并，然后四四歸并，然后是八八歸并，一直下去直到歸并了整個數(shù)組。

步驟

1. 申請空間，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列
2. 設(shè)定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置
3. 比較兩個指針?biāo)赶虻脑?，選擇相對小的元素放入到合并空間，并移動指針到下一位置
4. 重復(fù)步驟3直到某一指針到達(dá)序列尾
5. 將另一序列剩下的所有元素直接復(fù)制到合并序列尾

代碼實現(xiàn)

public class MergeSort {

    // 合并兩個已排好序的數(shù)組A[left...mid]和A[mid+1...right]
    void merge(Integer a[], int left, int mid, int right)
    {
        int len = right - left + 1;
        // 輔助空間O(n)
        Integer[] temp = new Integer[len];
        int index = 0;
        // 前一數(shù)組的起始元素
        int i = left;
        // 后一數(shù)組的起始元素
        int j = mid + 1;
        while (i <= mid && j <= right)
        {
            // 帶等號保證歸并排序的穩(wěn)定性
            temp[index++] = a[i] <= a[j] ? a[i++] : a[j++];
        }
        while (i <= mid)
        {
            temp[index++] = a[i++];
        }
        while (j <= right)
        {
            temp[index++] = a[j++];
        }
        for (int k = 0; k < len; k++)
        {
            a[left++] = temp[k];
        }
    }
    // 遞歸實現(xiàn)的歸并排序(自頂向下)
    void mergeSortRecursion(Integer a[], int left, int right)
    {
        // 當(dāng)待排序的序列長度為1時，遞歸開始回溯，進(jìn)行merge操作
        if (left == right)
        {
            return;
        }
        int mid = (left + right) / 2;
        mergeSortRecursion(a, left, mid);
        mergeSortRecursion(a, mid + 1, right);
        merge(a, left, mid, right);
    }

    // 非遞歸(迭代)實現(xiàn)的歸并排序(自底向上)
    void mergeSortIteration(Integer a[], int len)
    {
        // 子數(shù)組索引,前一個為A[left...mid],后一個子數(shù)組為A[mid+1...right]
        int left, mid, right;
        // 子數(shù)組的大小i初始為1,每輪翻倍
        for (int i = 1; i < len; i *= 2)
        {
            left = 0;
            // 后一個子數(shù)組存在(需要歸并)
            while (left + i < len)
            {
                mid = left + i - 1;
                // 后一個子數(shù)組大小可能不夠
                right = mid + i < len ? mid + i : len - 1;
                merge(a, left, mid, right);
                // 前一個子數(shù)組索引向后移動
                left = right + 1;
            }
        }
    }

    public static void main(String[] args){
        Integer[] a = {3,4,1,9,5,2,6,10,20,16,13,11,0};
        Integer[] b = {3,4,1,9,5,2,6,10,20,16,13,11,0};

        MergeSort sort = new MergeSort();
        // 遞歸實現(xiàn)
        sort.mergeSortRecursion(a, 0, a.length - 1);
        // 非遞歸實現(xiàn)
        sort.mergeSortIteration(b, b.length);

        System.out.println("a by MergeSort is " + Tool.arrayToString(a));
        System.out.println("b by MergeSort is " + Tool.arrayToString(b));

    }
}

public class Tool {
    public static <T> String arrayToString(T[] array){
        StringBuilder builder = new StringBuilder("[");
        for (int i = 0; i < array.length; i++){
            T item = array[i];
            builder.append(item + "");
            if (i != array.length - 1){
                builder.append(",");
            }
        }

        builder.append("]");
        return builder.toString();
    }

    public static <T> void exchange(T[] array, int i, int j){
        T temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

實現(xiàn)結(jié)果：

a by MergeSort is [0,1,2,3,4,5,6,9,10,11,13,16,20]
b by MergeSort is [0,1,2,3,4,5,6,9,10,11,13,16,20]