八大排序算法之归并排序

时间复杂度：O(Nlog(N))
额外空间复杂度：O(N)
是否可实现稳定性：是

思路：

归并排序用语言描述起来有点抽象，直接上例子。
比如数组{2，5，7，4}把它分成两个有序的部分 ，也就是{2,5} {4,7} 然后新建一个辅助数组，向这个辅助数组里加数，加入的数是两个数组相比较小的那个，2<5，2进入数组，5>4，4进入数组，然后7进入数组，大体就是这个思路，代码实现时需要用到递归，具体看代码注释

代码

 public static void mergeSort(int arr[]){
        if (arr==null||arr.length<2){
            return;
        }
        mergeSort(arr,0,arr.length-1);

    }

    public static void mergeSort(int arr[],int l,int r){
        //说明已经分成最小的范围了，得开始合并了
        if (l==r){
            return;
        }
        //找一个中间元素，当作左半区和右半区的分界线
        int mid = l + ((r-l)>>1);
        //递归分到最小，依次向上合并
        mergeSort(arr,l,mid);
        mergeSort(arr,mid+1,r);
        //合并 进入一个辅助数组并排序
        merge(arr,mid,l,r);
    }

    public static void merge(int arr[],int m,int l,int r){
        //辅助数组，长度为传进来数的个数
        int[] help = new int[r-l+1];
        //p1记录左半区的最小值
        int p1 = l;
        //p2记录右半区的最小值 m是分界线 [l,m]左半区 [m+1,r]右半区
        int p2 = m+1;
        int i = 0;
        while (p1<=m&&p2<=r){
            //开始向辅助数组中按照大小插入数，当左半区或者右半区没数了跳出循环，插入规则，每一次比较左半区和右半区
            //下标最前面的数的大小，小的进入数组
            help[i++] = arr[p1]<arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1<=m){
            //说明右半区已经全部插入了，左半区就直接插入就行
            help[i++] = arr[p1++];
        }
        while (p2<=r){
            help[i++] = arr[p2++];
        }

        for (int j = 0;j<help.length;j++) {
            //插入原数组
            arr[l + j] = help[j];
        }
    }