1.题目介绍

给你一个整数数组 nums，请你将该数组升序排列。

示例 1：
输入：nums = [5,2,3,1]
输出：[1,2,3,5]

示例 2：
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

2.题解

2.1 归并排序

思路

归并排序利用了分治的思想来对序列进行排序。对一个长为 n 的待排序的序列，我们将其分解成两个长度为 n/2 的子序列。
每次先递归调用函数使两个子序列有序，然后我们再线性合并两个有序的子序列使整个序列有序。

代码

注意几个点：
1.递归终止条件 l>=r
2.找中点的时候是mid = (l+r)>>1 而不是(l+r)>>2
3.注意给这里的临时数组tmp重新扩容！！！使用resize即可
4.归并归并，就是将分治后两个有序数组融合为一个更大的有序数组

class Solution {
    vector<int> tmp;
    void mergeSort(vector<int> &nums, int l, int r){
        if(l >= r) return;
        int mid = (l + r) >> 1;
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);
        int cnt = 0;
        int left = l, right = mid + 1;
        while(left <= mid && right <= r){
            if (nums[left] <= nums[right]) tmp[cnt++] = nums[left++];
            else tmp[cnt++] = nums[right++];
        }
        while(left <= mid) tmp[cnt++] = nums[left++];
        while(right <= r) tmp[cnt++] = nums[right++];
        for(int i = 0; i < cnt; i++){
            nums[l+i] = tmp[i];
        }
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        tmp.resize(n, 0);
        mergeSort(nums, 0, n-1);
        return nums;
    }
};