原理介绍

代码分析

纯模板：

class Solution {
public:
    // 自顶向下的归并排序;
    void mergeSort(vector<int> &arr, int size) {
        __mergeSort(arr, 0, size - 1);
    }
    // 递归 分解的过程, 知道递归到最小单元 ，两个数字的时候 开始合并;
    void __mergeSort(vector<int> &arr, int l, int r) {
        if (l >= r)return;
        int mid = l + ((r - l) >> 1);
        __mergeSort(arr, l, mid);
        __mergeSort(arr, mid + 1, r);
        // 优化1 ： 如果此时arr[mid] < arr[mid+1] 代表已经有序;
         if (arr[mid] < arr[mid + 1]) {
            merge(arr, l, mid, r);
        }
    }
    void merge(vector<int> &arr, int l, int mid, int r) {
        vector<int> aux(r - l + 1);// 辅助数组;
        for (int i = l; i <= r; i++) {
            aux[i - l] = arr[i];
        }
        int i = l, j = mid + 1;
        // [l....mid....r] 合并
        // 
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                arr[k] = aux[j - l];
                j++;
            } else if (j > r) {
                arr[k] = aux[i - l];
                i++;
            } else if (aux[i - l] < aux[j - l]) { //升序 降序由这个地方控制;
                arr[k] = aux[i - l];
                i++;
            } else if (aux[i - l] >= aux[j - l]) { //升序 降序由这个地方控制;
                arr[k] = aux[j - l];
                j++;
            } 
        }
    }
};
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    Solution slu;
    vector<int> arr = {6, 1, 3, 8, -2, 10};
    slu.mergeSort(arr, arr.size());
    for (int a:arr) {
        cout << a << " ";
    }
    return 0;
}