#include <iostream>
#include <fstream>
#include <stdlib.h>
using namespace std;

int v[500000];
int l[250000];
int r[250000];
ifstream a("algsort.in");
ofstream b("algsort.out");

void Merge(int st,int q,int dr)
{
    int i,j,k;
    int dim1=q-st+1;
    int dim2=dr-q;

    for(i=0; i<dim1; i++)l[i]=v[st+i];
    for(j=0; j<dim2; j++)r[j]=v[q+j+1];
    i=j=0;
    k=st;
    while(i<dim1&&j<dim2)
    {
        if(l[i]<=r[j])
        {
            v[k]=l[i];
            i++;
        }
        else
        {
            v[k]=r[j];
            j++;

        }
        k++;


    }

    while(i<dim1)
    {

        v[k]=l[i];
        i++;
        k++;

    }
    while(j<dim2)
    {

        v[k]=r[j];
        j++;
        k++;
    }
    cout<<"Asta este in Merge\n";
    for(i=st; i<=dr; i++)cout<<v[i]<<" ";
    cout<<endl;


}


void MergeSort(int st,int dr)
{
    for(int i=st; i<=dr; i++)cout<<v[i]<<" ";
    cout<<endl;
    if(st<dr)
    {
        int q=(st+dr)/2;
        MergeSort(st,q);
        MergeSort(q+1,dr);
        Merge(st,q,dr);

    }

}



int main()
{
    int n;
    a>>n;
    int i;
    for(i=0; i<n; i++)a>>v[i];
    MergeSort(0,n-1);
    for(i=0; i<n; i++)b<<v[i]<<' ';



    return 0;
}