#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

ifstream fin ("algsort.in");
ofstream fout ("algsort.out");
int v[500000],a[500000];
void mergesort(int v[], int st, int dr )
{
    if(st!=dr)
    {
        int mij=((st+dr)>>1);
        mergesort(v,st,mij);
        mergesort(v,mij+1,dr);
        int k,j,cpst=st;
        k=st;
        j=mij+1;
        while(k<=mij && j<=dr)
        {
            if(v[k]<v[j])
                a[st++]=v[k++];
            else
                a[st++]=v[j++];
            cout << a[st-1] << " ";
        }

        while(k<=mij)
        {
            a[st++]=v[k++];
            cout << a[st-1] << " ";
        }

        while(j<=dr)
        {
            a[st++]=v[j++];
            cout << a[st-1] << " ";
        }

        for(j=cpst;j<=dr;j++)
        {
            v[j]=a[j];

        }
        cout << '\n';

    }

}

int main()
{
    int i,n;
    fin >>n;
    for(i=0;i<n;i++)
        fin >> v[i];
    mergesort(v,0,n-1);
    for(i=0;i<n;i++)
        fout << v[i] << " ";
    return 0;
}