/**
 merge_sort = sortarea prin interclasare = este una dintre sortarile BUNE

Este bazata pe metoda de programare "Divide et Impera"

Skema este urmatoarea:


sort(li,lf) = are rolul de a sorta, in mod recursiv, "bucata" de vector dintre
indicii li shi lf.
              | - daca li==lf => bucata dintre indicii li,lf este sortata, deci NU mai
              |                  facem nimic
sort(li,lf):  | - in caz contrar: | - calc. mijl: m=(li+lf)/2
                                  | - apelam recursiv sort(li,m) shi sort(m+1,lf)
                                  | - bucatzile sortate mai sus se interclaseaza,
                                  |   avind grija sa punem elementele la loc in vector
                                  |   intre aceiashi indici, adik intre li shi lf.
*/
#include <cstdio>
using namespace std;
#define n_max 1000000
int a[n_max],b[n_max];//pe b  il folosim ca temporar la interclasare

void intercl(int li,int lf)
{//interclasam bucatzile li,m cu m+1,lf
    int m=(li+lf)/2,i,j,k;
    i=li;j=m+1;k=li;
    while(i<=m&&j<=lf)
        if(a[i]<a[j])b[k++]=a[i++];
        else b[k++]=a[j++];
    while(i<=m)b[k++]=a[i++];
    while(j<=lf)b[k++]=a[j++];
    for(i=li;i<=lf;i++)a[i]=b[i];
}

void merge_sort(int li,int lf)
{
    if(li<lf)
    {
        int m=(li+lf)/2;
        merge_sort(li,m);
        merge_sort(m+1,lf);
        intercl(li,lf);
    }
}

int main()
{
    FILE *f=fopen("algsort.in","r");
    int n,i;
    fscanf(f,"%d",&n);
    for(i=0;i<n;i++)
        fscanf(f,"%d",&a[i]);
    merge_sort(0,n-1);
    fclose(f);
    f=fopen("algsort.out","w");
    for(i=0;i<n;i++)
        fprintf(f,"%d ",a[i]);
    return 0;
}