$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$
笔记：
这一次的归并排序和上一个快速排序都一样，是分治的思想。
1. 同样也是确定分界点。$mid=(l+r)/2$
2. 递归排序$left$序列和$right$序列。
* 这里定义$left$序列为$a_l$到$a_{mid}$，$right$序列为$a_{mid+1}$到$a_r$。
3. 归并。最重要的一步，将$left$序列和$right$序列合二为一。

如何进行归并？

双指针算法

这是以后会学习的内容。
已经有有序序列$a$和$b$的时候：
1. 若$a_i$小于$b_i$，插入$a_i$。
2. 若$a_i$大于$b_i$，插入$b_i$。
3. 若$a_i$等于$b_i$，插入$a_i$。
4. 若$a$序列或$b$序列已经扫描结束，插入另一序列中的所有数。

代码：

#include <bits/stdc++.h>
using namespace std;
int n, a[100010], t[100010];
void merge_sort(int l, int r) {
    if (l >= r) return;
    int mid = l + r >> 1;
    merge_sort(l, mid); merge_sort(mid + 1, r);
    int i = l, j = mid + 1, tot = l;
    while (i <= mid && j <= r)
        if (a[i] <= a[j]) t[tot++] = a[i++];
        else t[tot++] = a[j++];
    while (i <= mid) t[tot++] = a[i++];
    while (j <= r) t[tot++] = a[j++];
    for (int i = l; i <= r; i++) a[i] = t[i];
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    merge_sort(1, n);
    for (int i = 1; i <= n; i++) cout << a[i] << " ";
    return 0;
}