#include<bits/stdc++.h>
using namespace std;
int a[100010],n;
mt19937 rng(time(0));
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    shuffle(a+1,a+1+n,rng);
    for(int base=1;base<=n;base<<=1){
        for(int i=1;i+base<=n;++i)
            if(a[i]>a[i+base])
                swap(a[i],a[i+base]);
    }
    for(int i=2,key,j;i<=n;++i){
        key=a[i];
        for(j=i-1;j>0&&a[j]>key;j--)
            a[j+1]=a[j];
        a[j+1]=key;
    }
    for(int i=1;i<=n;++i)
        cout<<a[i]<<" ";
    return 0;
}

吸氧可过。常数巨大。精神状态未知。

建议把 n 调到 5e5。