归并排序

归并排序采用了分治的思想，以及递归的写法。

[图解来源：排序算法：归并排序【图解+代码】]

合并两个有序数组的示意图：

[图解来源：图解排序算法(四)之归并排序]

代码实现：

class Solution {
    public int[] sortArray(int[] nums) {
        int[] tempArr = new int[nums.length];
        mSort(nums, tempArr, 0, nums.length-1);
        return nums;
    }
    public void mSort(int[] nums, int[] tempArr,int left, int right){
        //如果只有一个元素就不需要划分
        if(left < right){
            int mid = (left+right)/2;
            //递归划分左半区
            mSort(nums, tempArr, left, mid);
            //递归划分右半区
            mSort(nums, tempArr, mid+1, right);
            //合并
            merge(nums, tempArr, left, mid, right);
        }
    }
    public void merge(int[] nums, int[] tempArr,int left, int mid, int right){
        int l_pos = left;//标记左半区第一个元素
        int r_pos = mid + 1;//标记右半区第一个元素
        int pos = left;//临时数组元素下标
        while(l_pos <= mid && r_pos <= right){
            if(nums[l_pos] < nums[r_pos]){
                tempArr[pos++] = nums[l_pos++];
            }else{
                tempArr[pos++] = nums[r_pos++];
            }
        }
        //合并左半区剩余元素
        while(l_pos <= mid){
            tempArr[pos++] = nums[l_pos++];
        }
        //合并右半区剩余元素
        while(r_pos <= right){
            tempArr[pos++] = nums[r_pos++];
        }
        while(left <= right){
            nums[left] = tempArr[left];
            left++;
        }
    }
}