题解 | #排序#归并排序

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */

    void ms(vector<int>& q,int l,int r)
    {
        if(l>=r)return;
        int mid=l+r>>1;
        ms(q,l,mid),ms(q,mid+1,r);
        vector<int> tmp;//临时数组
        int i=l,j=mid+1;
        while(i<=mid&&j<=r)
        {
            if(q[i]<=q[j])tmp.push_back(q[i++]);
            else tmp.push_back(q[j++]);
        }
        while(i<=mid)tmp.push_back(q[i++]);
        while(j<=r)tmp.push_back(q[j++]);
        for(i=l,j=0;i<=r;i++,j++)q[i]=tmp[j];
    }
    vector<int> MySort(vector<int>& arr) {
        // write code here
        ms(arr,0,arr.size()-1);
        return arr;
    }
};