题解 | #排序#C++ 归并排序

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    // 使用递归形式的递归排序
    void Merge(vector<int>& arr, int l, int q, int r) {
        int left = l, right = q + 1;
        int temp[r - l + 1]; // 辅助函数
        int i = 0;
        // 三个while循环，进行两组数的逐个判断录入
        while(left <= q && right <= r) {
            temp[i++] = arr[left] <= arr[right] ? arr[left++] : arr[right++];
        }
        while(left <= q) {
            temp[i++] = arr[left++];
        }
        while(right <= r) {
            temp[i++] = arr[right++];
        }
        // 辅助数组填充完毕，直接循环赋给原数组
        for(int j = 0; j < i; ++j) {
            arr[l + j] = temp[j];
        }
    }


    void MergeSort(vector<int>& arr, int l, int r) {
        if (l == r) {
            return ;
        }
        // 对半划分
        int q = (l + r) / 2;
        // 子问题1和2
        MergeSort(arr, l, q);
        MergeSort(arr, q + 1, r);
        // 合
        Merge(arr, l, q, r);
    }


    vector<int> MySort(vector<int>& arr) {
        int len = arr.size();
        MergeSort(arr, 0, len - 1);
        return arr;
    }
};