2

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

int n;
int a[150005];
int b[150005];
void hebing(int l, int m, int r){
    //左边区域的左右边界
    int l1=l, r1=m;
    //右边区域的左右边界
    int l2=m+1, r2=r;
    //b数组的存储位置
    int cnt = l;
    //把左右区域的数字全部放入辅助数组
    //左右区域都还有数字
    while(l1<=r1 && l2<=r2){
        if(a[l1] <= a[l2]) b[cnt++] = a[l1++];
        else b[cnt++] = a[l2++];
    }
    //如果左区域还剩下数字
    while(l1<=r1) b[cnt++] = a[l1++];
    //如果右区域还剩下数字
    while(l2<=r2) b[cnt++] = a[l2++];

    for(int i=l; i<=r; i++) a[i] = b[i];
}

void msort(int l, int r){   //数组需要排序的左边界和右边界
    if(l<r){
        int mid = (l+r) / 2;
        //对左右区域再分
        msort(l, mid);
        msort(mid+1, r);
        //合并
        hebing(l, mid, r);
    }
}
int main(){
    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i];
    msort(1, n);  //归并排序

    for(int i=1; i<=n; i++) cout << a[i] << " ";
    return 0;
}