$\Huge\color{orchid}{点击此处获取更多干货}$

归并排序

归并排序也是考研热门，和快速排序类似，也是先划分再分别排序，只不过采用的是完全等分的方式，如果此处等分段数为$n$，那么此排序叫做$n$路归并排序，没有提到“$n$路”时默认2路归并排序。

首先是划分，先把序列划分成为若干不可再分的小段：

然后对这些小段分别排序，排序结果两两合并，划分顺序是①~④，那么合并顺序就是④~①：

可以看出，划分时的递归层数为$log_2(n)$，合并时最大长度为n，因此归并排序的时间复杂度是相对稳定的$O(n\*log_2(n))$，对比快速排序，如果枢值选中的恰好是序列的最大值，那么做升序排序时就会出现以下情况：

在快速排序部分中，原本演示用的序列正是这条，但如果选中值65作为枢值，划分就会严重不均等，体现不出“快速”特点，所以快速排序演示中将中值改为了45

C++ 代码

#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;

int* arr, * cache;//cache是用于合并的中转站

void mergeSort(int left, int right) {
    if(left >= right) {
        return;
    }
    //先无脑等分
    int mid = (left + right) / 2;
    mergeSort(left, mid);
    mergeSort(mid + 1, right);
    //然后合并左右两部分
    int ls = left, rs = mid + 1, id = 0;
    //下面就是合并两条有序线性表，数据结构必讲内容
    while(ls <= mid && rs <= right) {
        //谁小填谁
        if(arr[ls] <= arr[rs]) {
            cache[id] = arr[ls];
            ls++;
        }
        else {
            cache[id] = arr[rs];
            rs++;
        }
        id++;
    }
    //多出来的补到后边
    while(ls <= mid) {
        cache[id] = arr[ls];
        ls++;
        id++;
    }
    while(rs <= right) {
        cache[id] = arr[rs];
        rs++;
        id++;
    }
    //复制到原数组中
    copy(cache, cache + id, arr + left);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    arr = new int[n];
    cache = new int[n];
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    mergeSort(0, n - 1);
    for(int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    delete[] arr;
    delete[] cache;
    return 0;
}