题解 | #排序#

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

    vector<int> MySort(vector<int>& arr) {
        vector<int>temp(arr.size());
        merge_sort(arr, 0, arr.size() - 1,temp);
        return arr;
    }
    //归并排序
    void merge_sort(vector<int>& arr,int l,int r,vector<int>temp){
        if(l>=r)return ;
        int mid=((long long)l+r>>1);
        merge_sort(arr,l,mid,temp);
        merge_sort(arr,mid+1,r,temp);
        for(int k=l;k<=r;k++){
            temp[k]=arr[k];
        }
        int i=l,j=mid+1;
        for(int k=l;k<=r;k++)
            if(i==mid+1)arr[k]=temp[j++];
            else if(j==r+1||temp[i]<temp[j])arr[k]=temp[i++];
            else arr[k]=temp[j++];
    }
};