二路归并

参考文章：
https://blog.csdn.net/weixin_39651041/article/details/80010906

基本思想：将原始无序序列划分为子序列，先使每个子序列有序，然后将有序的子序列合并，得到完全有序的序列。

代码实现：

    public static void mergeSort(int[] nums,int low, int high){
        //对nums的判空在排序外层处理。否则每次递归都需要做重复无效的判断。
        if (low >= high){
            return;
        }
        int mid = (low + high)/2;
        mergeSort(nums,low,mid);
        mergeSort(nums,mid+1,high);
        merge(nums,low,mid,high);

    }

    public static void merge(int[] nums, int low,  int mid , int high){
        int[] temp = new int[nums.length];
        int lowStart = low;
        int highStart = mid + 1;
        int start = low; //注意此处的下标应该为入参中的low。而不是0.因为这里可能只对数组的部分范围内的数据做排序。
        while (lowStart <= mid && highStart <= high){//合并两个有序数组
            if (nums[lowStart] <= nums[highStart]){
                temp[start++] = nums[lowStart++];
            } else {
                temp[start++] = nums[highStart++];
            }
        }
        while (lowStart <= mid){
            temp[start++] = nums[lowStart++];
        }
        while (highStart <= high){
            temp[start++] = nums[highStart++];
        }
        while (low <= high){ //对该范围内的数据进行复制,注意需要包括等于。仅对该范围内的，其他范围内数据，temp中没有值！！！
            nums[low] = temp[low++];
        }
    }