题解 | #排序#

归并排序

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    vector<int> merge(vector<int> arr1,vector<int> arr2){
        vector<int> res;
        int i=0,j=0;
        while(i<arr1.size()&&j<arr2.size()){
            if(arr1[i]<arr2[j]) res.push_back(arr1[i]),i++;
            else res.push_back(arr2[j]), j++;
        }
        while(i<arr1.size()){
            res.push_back(arr1[i]);
            i++;
        }
        while(j<arr2.size()){
            res.push_back(arr2[j]);
            j++;
        }
        return res;
    }
    vector<int> sort(vector<int> arr,int start,int end){
        if(end==start) return {};
        if(end-start==1) return {arr[start]};
        int mid=start+(end-start)/2;
        vector<int> arr1,arr2;
        arr1=sort(arr,start,mid);
        arr2=sort(arr,mid,end);
        return merge(arr1,arr2);
    }
    vector<int> MySort(vector<int>& arr) {
        // write code here
        return sort(arr,0,arr.size());
    }
};