基础课学习笔记（汇总）{:target=”_blank”}

#include <iostream>
using namespace std;
const int N = 100010;
int n, a[N], temp[N];
void mergesort(int l, int r) {
    // 递归边界
    if (l >= r) return;
    // 步骤 ① 确定分界点 mid
    int mid = l + r >> 1;
    // 步骤 ② 递归左右区间
    mergesort(l, mid), mergesort(mid + 1, r);
    // 步骤 ③ 中 A 步 
    int i = l, j = mid + 1;
    // 步骤 ③ 中 B 步（辅助数组定义在全局变量里了）
    int k = l;
    // 步骤 ③ 中 C 步 循环终止条件：某个数组到头
    while (i <= mid && j <= r) 
        // 步骤 ③ 中 C 步 第一种情况
        if (a[i] <= a[j]) temp[k++] = a[i++];
        // 步骤 ③ 中 C 步 第二种情况
        else temp[k++] = a[j++];
    // 步骤 ③ 中 D 步（如果左区间还有元素）
    while (i <= mid) temp[k++] = a[i++];
    // 步骤 ③ 中 D 步（如果右区间还有元素）
    while (j <= r) temp[k++] = a[j++];
    // 步骤 ③ 中 E 步 复制回原数组
    for (int i = l; i <= r; i++) a[i] = temp[i];
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    mergesort(0, n - 1);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
}