又是一道模版，题解

#include <bits/stdc++.h>
using namespace std;

long long a[100005];
long long temp[100005];
int n;

// 归并操作
void merge(int l, int r, int mid) {
int i = l;
int j = mid + 1;
int k = 0;

// 合并左右两部分
while (i <= mid && j <= r) {
    if (a[i] <= a[j]) {
        temp[k++] = a[i++];
    } else {
        temp[k++] = a[j++];
    }
}

// 处理剩余的左半部分
while (i <= mid) {
    temp[k++] = a[i++];
}

// 处理剩余的右半部分
while (j <= r) {
    temp[k++] = a[j++];
}

// 将临时数组的内容拷贝回原数组
for (int q = 0; q < k; q++) {
    a[l + q] = temp[q];
}

// 输出当前状态
for (int i = 1; i <= n; i++) {
    cout << a[i];
    if (i < n) {
        cout << " ";
    }
}
cout << endl;
}

// 递归归并排序
void mergeSort(int l, int r) {
if (l >= r) return; // 如果只有一个元素或没有元素，直接返回

int mid = (l + r) / 2; // 计算中间位置
mergeSort(l, mid);     // 对左半部分递归排序
mergeSort(mid + 1, r); // 对右半部分递归排序
merge(l, r, mid);      // 合并左右两部分
}

int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}

mergeSort(1, n);

return 0;
}