题解 | #排序#

#include <vector>
//归并排序  时间O(n log n) 空间O(n) 稳定
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
void merge(vector<int>& nums,vector<int>& tmpArr,int left,int mid,int right){
    //标记左半区第一个未排序的元素
    int l_pos=left;
    //标记右半区第一个未排序的元素
    int r_pos=mid+1;
    //临时数组元素下标
    int pos=left;
    //合并
    while(l_pos<=mid&&r_pos<=right){
        if(nums[l_pos]<nums[r_pos]) tmpArr[pos++]=nums[l_pos++];
        else tmpArr[pos++]=nums[r_pos++];
    }
    //合并左半区剩余元素
    while(l_pos<=mid){
        tmpArr[pos++]=nums[l_pos++];
    }
    //合并右半区剩余元素
    while(r_pos<=right){
        tmpArr[pos++]=nums[r_pos++];
    }
    //把临时数组中的合并后的元素复制回原来的数组
    while(left<=right){
        nums[left]=tmpArr[left];
        left++;
    }
}
void msort(vector<int>& nums,vector<int>& tmpArr,int left,int right){
    if(left<right){//超过一个元素 则继续划分
        //找中间点
        int mid=(right-left)/2+left;
        //递归划分左半区
        msort(nums,tmpArr,left,mid);
        //递归划分右半区
        msort(nums,tmpArr,mid+1,right);
        //合并已划分的部分
        merge(nums,tmpArr,left,mid,right);
    }
}

    vector<int> MySort(vector<int>& arr) {
        // write code here
        vector<int> tmpArr(arr.size());
        msort(arr,tmpArr,0,arr.size()-1);
        return arr;
    }
};