复杂度

思路

1. 采用分治思想,先"分"再"治"
2. 分的过程即将数组分成若干个子部分,子部分最少数组元素为1
3. 治的过程即将子部分进行合并,两两合并到一组
4. 最终治到一组时排序结束

代码:

 public int[] mergeSort_1(int[] nums, int l, int r){

    if(l == r) return new int[]{nums[l]};//当分到子数组元素个数为1时返回该元素数组

    int mid = (l + r) / 2;

    int[] lArr = mergeSort_1(nums, l, mid);//左分
    int[] rArr = mergeSort_1(nums, mid + 1, r);//右分
    int[] merge = new int[r - l + 1];//合治数组

    //合治 i,j,k分别处理lArr,rArr与merge的下标
    int i = 0, j = 0, k = 0;
    while(i < lArr.length && j < rArr.length){
        if(lArr[i] < rArr[j]) merge[k++] = lArr[i++];
        else merge[k++] = rArr[j++];
    }
    while(i < lArr.length){
        merge[k++] = lArr[i++];
    }
    while(j < rArr.length){
        merge[k++] = rArr[j++];
    }
    return merge;
}