一、概念

归并排序（Merge Sort）是建设在归并操作上的一种无效，稳固的排序算法，该算法是采纳 分治法 的一个十分典型的利用。

将已有序的子序列合并，失去齐全有序的序列；即先使每个子序列有序，再使子序列段间有序。

二、排序过程

1、归并操作，指的是将两个程序序列合并成一个程序序列的办法。

如：数组 {6，202，100，301，38，8，1}

初始状态：6,202,100,301,38,8,1

第一次归并后：{6,202},{100,301},{8,38},{1}；

第二次归并后：{6,100,202,301}，{1,8,38}；

第三次归并后：{1,6,8,38,100,202,301}；

2、归并操作步骤如下：

（1）申请空间，大小为两个曾经排好序的序列之和，该空间用来做辅助数组

（2）设定两个指针，最后地位别离为两个曾经排序序列的起始地位

（3）比拟两个指针所指向的元素，抉择绝对小的元素放入到合并空间（相等抉择左组），并挪动指针到下一地位。

反复步骤 3 直到某一指针越界。将另一序列剩下的所有元素间接复制到合并序列（辅助数组）尾，将辅助数组数据拷贝回原数组。

三、Master 公式预计工夫复杂度

Master 公式：剖析递归函数的工夫复杂度，要求子问题规模统一

形如：
T(N) = a * T(N/b) + O(N^d)（其中 a、b、d 都是常数）的递归函数，能够间接通过 Master 公式来确定工夫复杂度
1）如果 log(b,a) < d，工夫复杂度为 O(N^d)
2）如果 log(b,a) > d，工夫复杂度为 O(N^log(b,a))
3）如果 log(b,a) == d，工夫复杂度为 O(N^d * logN)

依据 Master 公式可得 T(N) =2 * T(N/2) + O(N)

因为每次都是拆分为两个子问题，每个子问题占总规模的一半，且合并过程的工夫复杂度是 O(N)

可得 归并排序的工夫复杂度是 O(N*logN)。

四、代码实现

1、递归办法实现

    /**
     * 1. 递归办法实现
     */
    public static void mergeSort1(int[] arr) {if (arr == null || arr.length < 2) {return;}
        process(arr, 0, arr.length - 1);
    }

    private static void process(int[] arr, int l, int r) {if (l == r) {return;}
        int mid = l + ((r - l) >> 1);
        // 左组递归
        process(arr, l, mid);
        // 右组递归
        process(arr, mid + 1, r);
        // 合并
        merge(arr, l, mid, r);
    }

    private static void merge(int[] arr, int l, int m, int r) {
        // 辅助数组
        int[] help = new int[r - l + 1];
        int i = 0;

        // 左组地位
        int pL = l;
        // 右组地位
        int pR = m + 1;

        while (pL <= m && pR <= r) {
            // 谁小拷贝谁，相等的拷贝左组
            help[i++] = arr[pL] <= arr[pR] ? arr[pL++] : arr[pR++];
        }
        // pL 和 pR 有且只有一个会越界，也就是上面两个 while 只有一个会执行
        while (pL <= m) {help[i++] = arr[pL++];
        }
        while (pR <= r) {help[i++] = arr[pR++];
        }
        // 拷贝回原数组
        for (int j = 0; j < help.length; j++) {arr[l + j] = help[j];
        }
    }

2、迭代形式实现

定义一个步长，初始值为 1。从 0 地位的数开始，每两个步长的数 merge 完后拷贝回原数组，步长 *2；再从 0 地位的数开始，每两个步长的数 merge 完后拷贝回原数组，步长 *2……直到（步长 > 数组长度 / 2）

    /**
     * 2. 迭代形式实现归并排序
     * <p>
     * 步长调整次数 复杂度是 logN，每次调整步长都会遍历一遍整个数组 复杂度是 N，整个的工夫复杂度是 O(N*logN)
     */
    public static void mergeSort2(int[] arr) {if (arr == null || arr.length < 2) {return;}
        int N = arr.length;
        // 步长初始值
        int mergeSize = 1;

        // 步长不能超过数组长度
        while (mergeSize < N) {
            // 以后左组的第一个地位
            int L = 0;
            // 左组也不能超过数组长度
            while (L < N) {
                // 左组最初一个地位
                int M = L + mergeSize - 1;
                // 如果左组最初一个地位越界，表明左组都不够则不须要 merge
                if (M >= N) {break;}

                // 右组的最初一个地位
                // 右组第一个地位是 M + 1，满足个数要求则右组大小是 mergeSize，所以最初一个地位是 (M + 1) + mergeSize - 1
                // 不满足则是数组的最大地位 N - 1
                int R = Math.min(M + mergeSize, N - 1);

                // 目前 左组：L......M，右组：M+1......R
                merge(arr, L, M, R);

                // 下一次左组的地位（所以才须要判断 L < N）L = R + 1;
            }

            // 避免溢出
            // 当步长很凑近 N 的最大值时，乘以 2 扩充步长后，步长就溢出了
            // 不能取 >=，假如最大值是 9，mergeSize = 4 时就不会扩充步长了，然而 mergeSize = 8 时还有一次 merge，所以不能取 =
            if (mergeSize > N / 2) {break;}

            // 步长每次扩充 2 倍
            mergeSize <<= 1;
        }

    }