Java实现：归并排序

• 将两个有序的列表合并成一个有序的列表

                开辟一个长度等同于两个数组长度之和的新数组，并使用两个指针来遍历原有的两个数                  组，不断将较小的数字添加到新数组中，并移动对应的指针即可

• 拆分过程使用了二分的思想，这是一个递归的过程

为了减少在递归过程中不断开辟空间的问题，我们可以在归并排序之前，先开辟出一个临时空间，在递归过程中统一使用此空间进行归并即可

class Solution {
   //归并排序
    public int[] sortArray(int[] nums) {
        //临时数组result
        int[] result=new int[nums.length];
        //归并排序
        mergeSort(nums,0,nums.length-1,result);
        //此时nums与result相同
        return result;//此时nums与result相同
    }

    // 对 nums 的 [start, end] 区间归并排序
    public void mergeSort(int[] nums,int start,int end,int[] result){
        // 只剩下一个数字，停止拆分
        if(start==end) return;
        int middle=(start+end)/2;
        // 拆分左边区域，并将归并排序的结果保存到 result 的 [start, middle] 区间
        mergeSort(nums,start,middle,result);
        // 拆分右边区域，并将归并排序的结果保存到 result 的 [middle + 1, end] 区间
        mergeSort(nums,middle+1,end,result);
        // 合并左右区域到 result 的 [start, end] 区间
        merge(nums,start,end,result);
    }

    // 将 nums 的 [start, middle] 和 [middle + 1, end] 区间合并
    public void merge(int[] nums,int start,int end,int[] result){
        //分割
        int middle=(start+end)/2;
        // 数组 1 的首尾位置
        int start1=start;
        int end1=middle;
        // 数组 2 的首尾位置
        int start2=middle+1;
        int end2=end;
        // 用来遍历数组的指针
        int index1=start1;
        int index2=start2;
        // 结果数组的指针
        int resultIndex=start1;
        //比较插入结果数组
        while(index1<=end1 && index2<=end2){
            if(nums[index1]<=nums[index2]){
                result[resultIndex++]=nums[index1++];
            }else{
                result[resultIndex++]=nums[index2++];
            }
        }
        // 将剩余数字补到结果数组之后
        while(index1<=end1){
            result[resultIndex++]=nums[index1++];
        }
        while(index2<=end2){
            result[resultIndex++]=nums[index2++];
        }
        // 将 result 操作区间的数字拷贝到 arr 数组中，以便下次比较
        for(int i=start;i<=end;i++){
            nums[i]=result[i];
        }
    }
    
}