题解 | #排序#

归并排序：

1. 先不断地进行二分拆分；

2. 之后再将其合并起来。

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