题解 | #排序# 数组的归并排序

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