归并排序

归并，指合并，合在一起。归并排序（Merge Sort）是建立在归并操作上的一种排序算法。其主要思想是分而治之。

若将两个有序集合并成一个有序表，称为2-路归并，与之对应的还有多路归并。

怎么分

• 对于排序最好的情况来讲，就是只有两个元素，这时候比较大小就很简单，但是还是需要比较
• 如果拆分为左右各一个，无需比较即是有序的。

怎么治

借助一个辅助空数组，把左右两边的数组按照大小比较，按顺序放入辅助数组中即可。

以下面两个有序数组为例：

代码实现

public static  void  mergeSort(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 p1=L;
        int p2=M+1;
        //判断两边值是否越界
        while(p1<=M && p2<R){
            //当左边的值<右边的值  将左边的值拷贝到help里去
            //否则将右边的值拷贝到help里去
            help[i++] =arr[p1] <=arr[p2] ? arr[p1++] : arr[p2++];
        }
        //如果p1没有越界，那么将p1剩下的东西全部拷贝到help中去
        while(p1 <= M){
            help[i++] =arr[p1++];
        }
        //如果p2没有越界，那么将p2剩下的东西全部拷贝到help中去
        while(p2 <=R){
            help[i++]=arr[p2++];
        }

        for ( i = 0; i <help.length ; i++) {
            arr[L+i]=help[i];
        }
    }

时间复杂度

归并排序方法就是把一组n个数的序列，折半分为两个序列，然后再将这两个序列再分，一直分下去，直到分为n个长度为1的序列。然后两两按大小归并。如此反复，直到最后形成包含n个数的一个数组。

归并排序总时间 = 分解时间 + 子序列排好序时间 + 合并时间

无论每个序列有多少数都是折中分解，所以分解时间是个常数，可以忽略不计，则：

归并排序总时间 = 子序列排好序时间 + 合并时间

假设处理的数据规模大小为 n，运行时间设为：T(n)，则T(n) = n，当 n = 1时，T(1) = 1

由于在合并时，两个子序列已经排好序，所以在合并的时候只需要 if 判断即可，所以n个数比较，合并的时间复杂度为 n。

• 将 n 个数的序列，分为两个 n/2 的序列，则：T(n) = 2T(n/2) + n
• 将 n/2 个数的序列，分为四个 n/4 的序列，则：T(n) = 4T(n/4) + 2n
• 将 n/4 个数的序列，分为八个 n/8 的序列，则：T(n) = 8T(n/8) + 3n
• …
• 将 n/2k 个数的序列，分为2k个 n/2k 的序列，则：T(n) = 2kT(n/2k) + kn

当 T(n/2k) = T(1)时， 即n/2k = 1（此时也是把n分解到只有1个数据的时候），转换为以2为底n的对数：k = log2n，把k带入到T(n)中，得：T(n) = n + nlog2n。

使用大O表示法，去掉常数项 n，省略底数 2，则归并排序的时间复杂度为：O(nlogn)

算法稳定性

从原理分析和代码可以看出，为在合并的时候，如果相等，选择前面的元素到辅助数组，所以归并排序是稳定