//MERGE SORT


#include <stdio.h>
int n,n1=0,a[500000],b[500000];

    void merge(int p,int q)  //p=margine inferioara,q=margine superioara
    {
        //printf("%d %d\n",p,q);
        int mid,i,j;
        mid=(p+q)/2;      //m=mijloc

        if(p<q)              //daca vectorul are mai mult de 1 element se imparte iar
        {merge(p,mid);       //prima jum
        merge(mid+1,q);     //a doua jum

        i=p;                 //i ia val marginii inf,iar j marginii inferioare a celei de-a doua jum(mijloc+1)
        n1=1;
        j=mid+1;

        while(i<=mid && j<=q)   //interclasarea celor doi vectori
        {
            if(a[i]>a[j])        //baga a[j]
            {
                b[n1++]=a[j++];
            }
            else               //baga a[i]
            {
                b[n1++]=a[i++];
            }

        }

        while(i<=mid)   //completeaza din prima (jum pana la mid)
        b[n1++]=a[i++];


        while(j<=q)        //completeaza din a 2 a jumatate pana in marginea superioara(q)
        b[n1++]=a[j++];





        int k,t=p;             //t este pozitia de pe care incep cele 2 siruri interclasate
        for(k=1;k<=(q-p+1);++k)  //mutarea sirului sortat obtinut in vectorul a
        a[t++]=b[k];

        }
}

int main()



{
    FILE *f,*g;
    int i;
    f=fopen("algsort.in","r");
    g=fopen("algsort.out","w+");

    fscanf(f,"%d",&n);


    for(i=1;i<=n;++i)
    fscanf(f,"%d",&a[i]);

    merge(1,n);

    for(i=1;i<=n;++i)
        fprintf(g,"%d ",a[i]);


}