归并排序

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6+10;

int n, a[N];
int tmp[N];

inline void merge_sort(int *a, int l, int r) {
    if(l >= r) return ;
    int mid = (l+r)>>1;
    merge_sort(a, l, mid);
    merge_sort(a, mid+1, r);
    int cnt = 0, i = l, j = mid+1;
    while(i <= mid && j <= r) {
        if(a[i] <= a[j]) tmp[cnt++] = a[i++];
        else tmp[cnt++] = a[j++];
    }
    while(i <= mid) tmp[cnt++] = a[i++];
    while(j <= r) tmp[cnt++] = a[j++];
    for(int i = l, j = 0; i <= r; i++, j++) a[i] = tmp[j];
}

int main(int argc, char **argv) {
    cin.tie(0)->sync_with_stdio(false);
    
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    merge_sort(a, 1, n);
    for(int i = 1; i <= n; i++) cout << a[i] << ' ';
    
    return 0;
}