//Sortarea prin MergeSort

#include <iostream>
#include <fstream>
using namespace std;
int v[500001];
void merge(int v[],int st,int dr)
{//Interclasarea
    int i,j,k,n1,n2,mij;
    mij=st+(dr-st)/2;
    n1=mij-st+1;
    n2=dr-mij;
    int A[n1],B[n2];
    for(i=0;i<=n1-1;i++)
    {
        A[i]=v[st+i];//punem in A, elementele de la st pana la mijloc
    }
    for(j=0;j<=n2-1;j++)
    {
        B[j]=v[mij+1+j];//punem in B elementele de la mijloc pana la dr
    }
    i=0;
    j=0;
    k=st;
    while(i<=n1-1 && j<=n2-1) //interclasam
    {
        if (A[i]<=B[j]) //punem cel mai mic element dintre cei 2 vectori
        {
            v[k]=A[i];
            i++;
        }
        else
        {
            v[k]=B[j];
            j++;
        }
        k++;
    }
    while(i<=n1-1) //daca raman elemente in vectorul A, le plasam si pe acestea
    {
        v[k]=A[i];
        i++;
        k++;
    }
    while(j<=n2-1)//daca rama in B, le plasam si pe acestea
    {
        v[k]=B[j];
        j++;
        k++;
    }
}
 
void MergeSort(int v[], int st, int dr)
{
    if (st<dr)
    {
        int mij=st+(dr-st)/2;//mij preia valoarea mediei intre st si dr
        MergeSort(v,st,mij);//apelam mergesort pentru prima jumatate
        MergeSort(v,mij+1,dr);//apelam mergesort pentru a doua jumatate
        merge(v,st,dr);//interclasam
    }
}
int main()
{
    int N,i;
    ifstream fin("algsort.in");
    ofstream fout("algsort.out");
    fin>>N;//citim dimensiunea tabloului
    for(i=0;i<=N-1;i++)
    {
        fin>>v[i];//citim elementele
    }
    MergeSort(v,0,N-1);//sortam
    for(i=0;i<=N-1;i++)
    {
        fout<<v[i]<<" ";//afisam
    }
    return 0;
}