归并排序

归并排序在经典递归实现中需要的额外空间相对较多。这是因为在归并排序的过程中，需要与原始数组大小相同的额外空间来存储临时合并的数组。所以，其空间复杂度为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;}
}