归并排序（Java-递归版）

         归并排序是采用分治法（Divide and Conquer）的一个非常典型的应用(典型的分而治之思想的算法 )

• 分解：将n个元素分成个含n/2个元素的子序列。

• 排序：用合并排序法对两个子序列递归的排序。

• 合并：合并两个已排序的子序列已得到排序结果。

public static int[] MergerSort(int[] arr){
        int len = arr.length;           //统计排序个数
        int[] result = new int[len];       给其开辟新内存空间
        MergerSortRecursion(arr,result,0,len-1);
        return arr;
    }

    private static void MergerSortRecursion(int[] arr, int[] result, int start, int end) {
        //分割  到末结束分割进行第二步走
        if(start>=end){
            return;
        }
        //len  统计分割后每个子序的个数         mid 是start和end中间下标
        int len = end - start , mid = (len >> 1) + start;
        int start1 = start , end1 = mid ;
        int start2 = mid +1,end2 = end;
        //递归分割
        MergerSortRecursion(arr,result,start1,end1);
        MergerSortRecursion(arr,result,start2,end2);
        //解决
        int k=start;
        while (start1 <= end1 && start2 <= end2){   //遍历子序每个待排序数值
            result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++] ;
        }
        while (start1 <= end1){     //等值 后续  +++
            result[k++]=arr[start1++];
        }
        while (start2 <= end2){
            result[k++]=arr[start2++];
        }
        //更新数组内容
        for (int i = start; i <= end; i++) {
            arr[i] = result[i];
        }
    }

归并和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

有疑问的留言互动!!!

Thanks!!