题解 | #归并排序#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    vector<int> MySort(vector<int>& arr) {
        sortseperate(arr, 0, arr.size()-1);
        return arr;
    }
    void sortseperate(vector<int>& arr,int l,int r){//分治
        if(l==r) return;//终止条件
        int m = (l+r)/2;
        sortseperate(arr, l, m);
        sortseperate(arr,m+1,r);//每次都m+1
        merge(arr,l,m,r);
    }
    void merge(vector<int>& arr,int l,int m,int r){//合并
        int* ans = new int[r-l+1];//注意这里的int[r-l+1]最后delete带[]
        int left = l,right = m+1;
        int i = 0;
        while(left<=m && right <=r){//这里注意是&&，就是一个不满足都不行
            ans[i++] = arr[left]<=arr[right]?arr[left++]:arr[right++];
        }
        while(left<=m) ans[i++] = arr[left++];
        while(right<=r) ans[i++] = arr[right++];
        for(int i = 0;i<r-l+1;i++){
            arr[l+i] = ans[i];
        }
        delete[] ans;
    }
};