十大排序--归并排序

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

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

图片来源于：https://www.runoob.com/w3cnote/merge-sort.html

public class MergeSort {
    public static void main(String[] args) {
        int[] nums = new int[]{711,42,333,6,7555,85,93,24,30,177};
        System.out.println(Arrays.toString(mergeSort(nums,0,nums.length-1)));
    }

    static int[] mergeSort(int[] nums,int start,int end) {
        // 退出递归条件 左指针与右指针重合，即仅有一个元素
        // 从左、右仅有一个元素开始合并，单个元素默认为有序
        if(start==end) return new int[]{nums[start]};
        // 获取中间指针
        int mid = (start + end) / 2;
        // 左侧有序数组
        int[] left = mergeSort(nums, start, mid);
        // 右侧有序数组
        int[] right = mergeSort(nums, mid+1, end);
        // 进行合并
        return merge(left,right);
    }

    static int[] merge(int[] left, int[] right) {
        // 合并后的临时数组，长度为两个数组长度之和
        int[] temp = new int[left.length + right.length];
        // i:左数组指针；j：右数组指针；t：临时数组指针
        int i = 0, j = 0, t = 0;
        // 当左指针和右指针都未达到边界时，两数组元素比较
        while (i < left.length && j < right.length) {
            // 左小于右--> 先放左指针对应的值
            if(left[i] 
参考：
 
https://www.runoob.com/w3cnote/merge-sort.htmlhttps://www.cnblogs.com/chengxiao/p/6194356.html