#include <stdio.h>
#include <stdlib.h>
#define StartingSize 16
#define VectorType int

typedef struct _CC_VECTOR{
    VectorType *V;
    int Size, Fpoz, Lpoz;
    /// Fpoz - prima pozitie libera din vector
    /// Lpoz - ultima pozitie libera din vector
} CC_VECTOR;

int VecCreate( CC_VECTOR **Vector )
{
    ///Alocam memorie dinamic pentru structura de vector si pentru vectorul propriuzis din acesta
    *Vector = ( CC_VECTOR * )malloc( sizeof( CC_VECTOR ) );
    if( *Vector == 0 ) return -1;
    (*Vector) -> V = ( VectorType * )malloc( sizeof( VectorType ) *  StartingSize );
    if( (*Vector) -> V == 0 ) return -2;
    (*Vector) -> Size = StartingSize;
    (*Vector) -> Fpoz = StartingSize / 2 - 1;
    (*Vector) -> Lpoz = StartingSize / 2;
    return 0;
}

int VecDestroy( CC_VECTOR **Vector )
{
    free( *Vector );
    return 0;
}

int Resize( CC_VECTOR *Vector )
{
    ///Dublez marimea vectorului si il recentrez folosind un auxiliar
    VectorType *aux;
    aux = ( VectorType * )malloc( sizeof( VectorType ) * ( Vector -> Size ) * 2 );
    if( aux == 0 ) return -1;
    Vector -> Size = Vector -> Size * 2;
    int l = Vector -> Lpoz - Vector -> Fpoz - 1;
    l = Vector -> Size / 2 - l / 2;
    int n = l + Vector -> Lpoz - Vector -> Fpoz - 1;
    for( int i = l ; i < n ; i++ )
    {
        //GetValueByIndex( Vector , i - l , aux + i );
        //aux[ i ] = Vector -> V[ i - l ];
        aux[ i ] = Vector -> V[ Vector -> Fpoz + i - l + 1 ];
    }
    free( Vector -> V );
    Vector -> V = aux;
    Vector -> Fpoz = l - 1;
    Vector -> Lpoz = n;
    return 0;
}

int VecInsertTail( CC_VECTOR *Vector, VectorType Value )
{
    if( Vector -> Lpoz == Vector -> Size )
    {
        if( Resize( Vector ) == -1 ) return -1;
    }
    Vector -> V[ Vector -> Lpoz ] = Value;
    Vector -> Lpoz = Vector -> Lpoz + 1;
    return 0;
}

int VecInsertHead( CC_VECTOR *Vector, VectorType Value )
{
    if( Vector -> Fpoz == -1 )
    {
        if( Resize( Vector ) == -1 ) return -1;
    }
    Vector -> V[ Vector -> Fpoz ] = Value;
    Vector -> Fpoz = Vector -> Fpoz - 1;
    return 0;
}

int VecInsertAfterIndex( CC_VECTOR *Vector, int Index, VectorType Value )
{
    if( Vector -> Fpoz == -1 && Vector -> Lpoz == Vector -> Size )
    {
        if( Resize( Vector ) == -1 ) return -1;
    }
    ///Daca este mai mult spatiu in stanga voi "shift-a" vectorul in stanga, altfel in dreapta
    if( Vector -> Fpoz + 1 > Vector -> Size - Vector -> Lpoz )
    {
        int f = Vector -> Fpoz;
        for( int i = f ; i <= Vector -> Fpoz + Index ; i++ )
        {
            Vector -> V[ i ] = Vector -> V[ i + 1 ];
        }
        Vector -> Fpoz = Vector -> Fpoz - 1;
        Vector -> V[ Vector -> Fpoz + Index + 2 ] = Value;
    }
    else
    {
        for( int i = Vector -> Lpoz ; i > Vector -> Fpoz + Index + 1 ; i-- )
        {
            Vector -> V[ i ] = Vector -> V[ i - 1 ];
        }
        Vector -> Lpoz = Vector -> Lpoz + 1;
        Vector -> V[ Vector -> Fpoz + Index + 2 ] = Value;
    }
    return 0;
}

int VecRemoveByIndex( CC_VECTOR *Vector, int Index )
{
    ///Vom "shift-a" vector din partea cu mai putine elemente
    if( Vector -> Fpoz + 1 < Vector -> Size - Vector -> Lpoz )
    {
        for( int i = Vector -> Fpoz + Index ; i > Vector -> Fpoz + 1 ; i-- )
        {
            Vector -> V[ i ] = Vector -> V[ i - 1 ];
        }
        Vector -> Fpoz = Vector -> Fpoz + 1;
    }
    else
    {
        for( int i = Vector -> Fpoz + 1 ; i < Vector -> Lpoz ; i++ )
        {
            Vector -> V[ i ] = Vector -> V[ i + 1 ];
        }
        Vector -> Lpoz = Vector -> Lpoz - 1;
    }
    return 0;
}

int GetValueByIndex( CC_VECTOR *Vector, int Index, VectorType *Value )
{
    if( Index < 0 || Index >= Vector -> Lpoz - Vector -> Fpoz - 1 )
        return -1;
    (*Value) = Vector -> V[ Vector -> Fpoz + Index + 1 ];
    return 0;
}

int GetCount( CC_VECTOR *Vector )
{
    return Vector -> Lpoz - Vector -> Fpoz - 1;
}

int VecClear( CC_VECTOR *Vector )
{
    Vector -> Fpoz = Vector -> Size / 2;
    Vector -> Lpoz = Vector -> Fpoz + 1;
    return 0;
}

int MergeSort( CC_VECTOR *Vector , int Left, int Right )
{
    if( Right - Left == 0 ) return 0;
    int Middle = Left + ( Right - Left ) / 2;
    if( MergeSort( Vector , Left , Middle ) == -1 ) return -1;
    if( MergeSort( Vector , Middle + 1 , Right ) == -1 ) return -1;

    int A = Left, B = Middle + 1, i = 0; /// pentru interclasare se vor folosi indicii A ( jumatatea stanga ) si B ( jumatatea dreapta )
    VectorType *aux; /// si un vector auxiliar
    aux = ( VectorType * )malloc( ( Right - Left + 1 ) * sizeof( VectorType ) );
    if( aux == 0 ) return -1;
    while( A <= Middle || B <= Right )
    {
        if( A == Middle + 1 )
        {
            aux[ i++ ] = Vector -> V[ B++ ];
        }
        else if( B == Right + 1 )
        {
            aux[ i++ ] = Vector -> V[ A++ ];
        }
        else if( Vector -> V[ A ] <= Vector -> V[ B ] )
        {
            aux[ i++ ] = Vector -> V[ A++ ];
        }
        else
        {
            aux[ i++ ] = Vector -> V[ B++ ];
        }
    }
    for( int i = Left ; i <= Right ; i++ )
    {
        Vector -> V[ i ] = aux[ i - Left ];
    }
    free( aux );
    return 0;
}

int VecSort( CC_VECTOR *Vector )
{
    return MergeSort( Vector , Vector -> Fpoz + 1 , Vector -> Lpoz - 1 );
}

int main()
{
    FILE *fin = fopen( "algsort.in" , "r" );
    FILE *fout = fopen( "algsort.out" , "w" );
    int n,i,x;
    CC_VECTOR *v;
    VecCreate( &v );
    fscanf( fin , "%d" , &n );
    for( int i = 1 ; i <= n ; i++ )
    {
        fscanf( fin , "%d" , &x );
        VecInsertTail( v , x );
    }
    VecSort( v );
    for( int i = 0 ; i < n ; i++ )
    {
        GetValueByIndex( v , i , &x );
        fprintf( fout , "%d " , x );
    }
}