Java实现：归并排序_归并排序 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);
        // 拆分右边区域，并将归并排序的结