912. 归并排序

给出一个无序数组，将该数组升序排列。

1. 归并排序。将两个有序数组合并成一个有序数组，方法有两种，如果开辟一个O(M+N)空间的数组来保存临时有序数组，时间是O(n)；或者用直接插入排序，时间O(n^2)。这里给出的是直接插入的方法:

public int[] sortArray(int[] nums) {
    mergeSort(nums,0,nums.length-1);
    return nums;
}
public void mergeSort(int[] nums,int low,int high)
{
    if(low==high) return ;
    int mid=(low+high)/2;
    mergeSort(nums,low,mid);
    mergeSort(nums,mid+1,high);
    int i=mid+1,j=low;
    while(i<=high)
    {
        while(j<i&&nums[i]>=nums[j])j++;
        if(j==i) break;
        int temp=nums[i];
        for(int k=i-1;k>=j;k--)
        nums[k+1]=nums[k];
        nums[j]=temp;
        i++;
    }
    return ;
}