#include <cmath>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#define InFile "algsort.in"
#define OutFile "algsort.out"

/*
 *
 */

using namespace std;
ifstream in;
ofstream out;
class IntroSort
{
    unsigned *v;
    unsigned size, till;
    inline void swap( unsigned, unsigned );
    inline unsigned medianof3( unsigned, unsigned, unsigned );
    void downheap( unsigned, unsigned );
    void make_heap( unsigned, unsigned );
    unsigned partition( int, int, unsigned );
public:
    IntroSort();
    ~IntroSort();
    void push( istream& );
    void output( ostream& );
    inline unsigned getsize();
    void HeapSort( unsigned, unsigned );
    void introsort( unsigned, unsigned, unsigned  );
    void InsertionSort( unsigned, unsigned );
};
IntroSort::IntroSort()
{till=size=0;  //there is no element in vector
    v=(unsigned*)malloc( sizeof( unsigned ) ); // give memory
}
IntroSort::~IntroSort()
{
    free(v); //free the memory
}
void IntroSort::push( istream& in )
{++size; // a new element is inserted
    v=(unsigned*)realloc( (void*)v, size*sizeof( unsigned ) ); // creating enough space for one more element
    in>>v[size-1]; //reading date
}
void IntroSort::output( ostream& out )
{
   copy( v, v+size, ostream_iterator< unsigned >( out, " " ) ); // outputing the array
}
inline unsigned IntroSort::getsize()
{
    return size;
}
inline void IntroSort::swap( unsigned a, unsigned b ) // exchanging 2 element v[a] and v[b]
{unsigned aux=v[a];
    v[a]=v[b];
    v[b]=aux;
}
/*              Median of three
a>b|         true        |       false
---+---------------------+----------------------
b>c| true |     false    | true         | false
---+---------------------+----------------------
a>c|  X   | true | false | true | false |  X
---+---------------------+----------------------
   |  b   |  c   |  a    |  a   |  c    |  b
*/
inline unsigned IntroSort::medianof3( unsigned a, unsigned b, unsigned c )
{
    if( v[a] > v[b] )
    {
        if( v[b] > v[c] )
          return v[b];
        else if( v[a] > v[c] )
               return v[c];
        return v[a];
    }
    else if( v[b] > v[c] )
         {
             if( v[a] > v[c] )
               return v[a];
             else return v[c];
         }
    return v[b];
}
unsigned IntroSort::partition( int st, int dr, unsigned x )
{
    while( true )
    {
        while( v[st] <= x ) ++st;
        --dr;
        while( x <= v[dr] ) --dr;
        if( !( st < dr ) )
          return st;
        swap( st, dr );
        ++st;
    }
}
void IntroSort::downheap( unsigned begin, unsigned end )
{
    for( unsigned root=2*begin+1; root < end; )
    {
        if( root+1 < end && v[root] < v[root+1] ) ++root;
        if( v[root] <= v[begin] ) return; // if it is heap stop
        swap( root, begin );
        begin=root;
        root=2*begin+1;
    }
}
void IntroSort::make_heap( unsigned start, unsigned end )
{
    for( unsigned begin=end/2-1; begin > start; --begin )
       downheap( begin, end );
    downheap( start, end );
}
void IntroSort::HeapSort( unsigned begin, unsigned end )
{
    make_heap( begin, end );
    for( end=end-1; end > begin; --end )
    {
        swap( begin, end );
        downheap( begin, end );
    }
    swap( begin, end );
    downheap( begin, end );
}

void IntroSort::introsort( unsigned st, unsigned dr, unsigned depth_limit )
{
    while( dr - st > till )
    {
        if( !depth_limit )
        {
            HeapSort( st, dr );
            return ;
        }
        --depth_limit;
        unsigned m=partition( st, dr, medianof3( st, (st+dr)/2+1, dr-1 ) );
        introsort( m, dr, depth_limit );
        dr=m;
    }
}
void IntroSort::InsertionSort( unsigned st, unsigned dr )
{
    unsigned i, j, aux;
    for( i=st; i < dr; ++i )
    {
        j=i;
        aux=v[i];
        while( j != st && aux < v[j-1] )
        {
            v[j]=v[j-1];
            --j;
        }
        v[j]=aux;
    }
}
int main()
{int N;
 IntroSort a;
    in.open( InFile );
    in>>N;
    while( N-- )
    {
        a.push( in );
    }
    out.open( OutFile );
    a.introsort( 0, a.getsize(), log(a.getsize())/log(2) );
    a.InsertionSort( 0, a.getsize() );
    a.output( out );
    return EXIT_SUCCESS;
}