基本思想

歸并排序是分而治之的算法思想的實際應(yīng)用，其排序過程是將待排序序列逐層分解直到最后只有一個元素，然后在反向合并。

遞歸版歸并排序

如上圖所示

1. 被分解為，。
2. 被分解為，
3. 被分解為，，此時各組只有一個元素不再繼續(xù)分解。
4. 合并，成。
5. 分解為，，此時各組只有一個元素不再繼續(xù)分解。
6. 合并，成.
7. 合并 4,6結(jié)果，成。
8. 分解成,。
9. 分解成,，此時各組只有一個元素不再繼續(xù)分解。
10. 合并,成。
11. 合并,成。
12. 合并7,11結(jié)果，成排序結(jié)束。
    在整個排序過程中分解過程較為簡單，就是一分為二，核心在合并過程，即將兩個有序序列合并為一個有序序列。

源碼實現(xiàn)

遞歸版

    static void merge(T arr[], int size) {
        merge(arr, 0, size - 1);
    }
    static void merge(T arr[], int L, int R) {
        if (L >= R) {
         //  遞歸結(jié)束
            return;
        }
        int M = L + (R - L) / 2;
        merge(arr, L, M);
        merge(arr, M + 1, R);
        merge(arr, L, M, R);
    }
    static void merge(T arr[], int L, int M, int R) {

        T *aux = new T[R - L + 1];
        for (int i = L; i <= R; i++) {
            aux[i-L] = arr[i];
        }
        // i 索引歸并后的數(shù)組[L, R]，j索引aux左半邊數(shù)組[0,M-L],k索引aux
        // 右半邊[M-L+1, R-L]
        for (int i = L, j=0, k=M-L+1; i <= R; i++) {
            if (j > M-L) {
                arr[i] = aux[k++];
            }
            else if (k > R - L) {
                arr[i] = aux[j++];
            }
            else if (aux[j] > aux[k]) {
                arr[i] = aux[k++];
            }
            else {
                arr[i] = aux[j++];
            }
        }
        delete[]aux;
    }

迭代版

    static void merge_bu(T arr[], int size) {
        for (int sz = 1; sz < size; sz += sz) {
            for (int i = 0; i < size - sz; i+=sz*2) {
                merge(arr, i, i + sz - 1, size-1< i + 2 * sz - 1?size-1: i + 2 * sz - 1);
            }
        }
    }