//Merge Sort

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

int a[500000],n;
void Citire_date(int a[],int &n)
{
    ifstream f;
    int i;
    f.open("algsort.in");
    f>>n;
    for(i=1;i<=n;i++)
        f>>a[i];
    f.close();

}

void Merge(int s,int m,int d)
{
    int b[500000]; //vector auxiliar
    int bi; //indicele pentru vector auxiliar
    bi=s;

    int i,j;

    i=s;
    j=m+1;

    while(i<=m && j<=d)
    {
        if(a[i]<=a[j]){
            b[bi]=a[i];
            i++;
        }else{
            b[bi]=a[j];
            j++;
        }
        bi++;
    }

    int k;

    if(i>m)
    {
        for(k=j;k<=d;k++)
        {
            b[bi]=a[k];
            bi++;
        }

    }else{
        for(k=i;k<=m;k++){
            b[bi]=a[k];
            bi++;
        }
    }
    for(k=s;k<=d;k++)
        a[k]=b[k];
}
void MergeSort(int s,int d)
{
    int m;
    if(s<d)
    {
        m=(s+d)/2;
        MergeSort(s,m);
        MergeSort(m+1,d);
        Merge(s,m,d);
    }
}
void Afisare(int a[],int n)
{
    int i;
    ofstream g("algsort.out");
    for(i=1;i<=n;i++)
        g<<a[i]<<" ";
    g.close();
}
int main()
{
    Citire_date(a,n);
    MergeSort(1,n);
    Afisare(a,n);
    return 0;
}