归并排序

归并排序在经典递归实现中需要的额外空间相对较多。这是因为在归并排序的过程中，需要与原始数组大小相同的额外空间来存储临时合并的数组。所以，其空间复杂度为O(n)，其中n表示待排序数组的长度。在递归过程中，需要创建临时数组来存储分割后的子数组，这些临时数组会随着递归的进行不断地被创建和释放。

相比快速排序算法，归并排序在任何情况下都是O（nlogn），而快速排序在最坏的情况下是O（n的平方）

算法代码如下：

class Solution {
    public int[] sortArray(int[] nums) {
            return mergeSort(nums, 0, nums.length-1);
    }
    public static int[] mergeSort(int[] nums, int l, int r){

        if(l==r){
            int[] newsz=new int[1];
            newsz[0]=nums[l];
            return newsz;
        }
        int mid=(l+r)/2;
        int[] mergeSort1 = mergeSort(nums, l, mid);
        int[] mergeSort2 = mergeSort(nums, mid + 1, r);
        int[] sum=new int[mergeSort1.length+mergeSort2.length];

        int m=0,i=0,j=0;
        while (i<mergeSort1.length&&j<mergeSort2.length) {
            if (mergeSort1[i] <= mergeSort2[j]) {
                sum[m++] = mergeSort1[i++];
            } else {
                sum[m++] = mergeSort2[j++];
                }
            }
            while (j<mergeSort2.length){
                sum[m++]=mergeSort2[j++];
            }
            while (i<mergeSort1.length){
                sum[m++]=mergeSort1[i++];
            }
        return sum;
    }
}