基本思想

归并排序是分而治之的算法思想的实际应用，其排序过程是将待排序序列逐层分解直到最后只有一个元素，然后在反向合并。

递归版归并排序

如上图所示

1. 被分解为，。
2. 被分解为，
3. 被分解为，，此时各组只有一个元素不再继续分解。
4. 合并，成。
5. 分解为，，此时各组只有一个元素不再继续分解。
6. 合并，成.
7. 合并 4,6结果，成。
8. 分解成,。
9. 分解成,，此时各组只有一个元素不再继续分解。
10. 合并,成。
11. 合并,成。
12. 合并7,11结果，成排序结束。
    在整个排序过程中分解过程较为简单，就是一分为二，核心在合并过程，即将两个有序序列合并为一个有序序列。

源码实现

递归版

    static void merge(T arr[], int size) {
        merge(arr, 0, size - 1);
    }
    static void merge(T arr[], int L, int R) {
        if (L >= R) {
         //  递归结束
            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 索引归并后的数组[L, R]，j索引aux左半边数组[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);
            }
        }
    }