归并排序思路梳理：

  1.  归并排序是通过不断将原有数据一分为二，然后再按顺序合并的算法。逻辑主要涉及到两方面，即二分与合并
  2. 边界条件：当数组中只有一个数，则说明该数是有序的
        end-start<2  

核心代码：

  // 占用空间较少的合并方法
public static void mergeSort(int nums[],int left,int right){
        if(right-left<2){
            return;
        }
        int mid = (left+right)/2;
        mergeSort(nums,left,mid);
        mergeSort(nums,mid,right);
        merge(nums,left,mid,right);
    }


    public static void merge(int[] nums,int left,int mid,int right){
        //+2主要是有两个位置用来存储哨兵
        int[] temp = new int[right-left+2];
        temp[mid-left] = temp[right-left+1]=Integer.MAX_VALUE;
//        for(int i=left;i<mid;i++){
//            temp[i-left] = nums[i];
//        }
//       //这两步赋值临时表的，因为临时表长度与数组原长度不一致，所以计算起、终下标需要取一下巧。 可以理解为left为基本偏移量。mid-left为左边数组的长度。
//        for(int i=mid;i<right;i++){
//            temp[i-left+1] = nums[i];
//        }
        for(int i =0;i<mid-left;i++){
            temp[i] = nums[i+left];
        }
        for(int i=mid-left;i<right-left;i++){
            temp[i+1] = nums[i+left];
        }

        int leftIndex = 0;
        int rightIndex = (mid-left)+1;
        for(int i = left;i<right;i++){
            if(temp[leftIndex] < temp[rightIndex]){
                nums[i] = temp[leftIndex++];
            }else{
                nums[i] = temp[rightIndex++];
            }
        }

// 第二种合并方法，直接新建子数组用来存储要操作的数据。因为起始下标都是0，操作起来更加清晰明确。个人比较喜欢这种操作
// 在目前计算机硬件配置都比较高的情况，没必要为了一点点性能去牺牲代码的美观和可读性。 如果实在有性能瓶颈才针对性的进行调优即可。
public static void merge2(int[] nums,int left,int mid,int right){
        int[] leftArr = Arrays.copyOfRange(nums, left, mid+1);
        int[] rightArr = Arrays.copyOfRange(nums, mid, right+1);

        leftArr[leftArr.length-1] = rightArr[rightArr.length-1]= Integer.MAX_VALUE;

        int leftIndex = 0;
        int rightIndex = 0;
        for(int i=left;i<right;i++){
            if(leftArr[leftIndex]<rightArr[rightIndex]){
                nums[i] = leftArr[leftIndex++];
            }else{
                nums[i] = rightArr[rightIndex++];
            }
        }
    }

    }