题解 | #排序#

归并排序：先分裂后整合，依据这个思路来写代码；

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