/* 
 * File:   main.cpp
 * Author: speedemon
 *
 * Created on October 2, 2009, 7:09 PM
 */
#include <fstream>
#include <cstdlib>
#include <vector>
#define InFile "algsort.in"
#define OutFile "algsort.out"

/*
 * 
 */

using namespace std;
ifstream in;
ofstream out;
class array
{
    int *v;
    int size;
public:
    array();
    ~array();
    inline void swap( int, int );
    inline int getsize(); //retuns the size of array
    inline bool check( int, int ); // checks if v[a] <= v[b]
    inline bool check_strict( int, int ); // checks if v[a] < v[b]
    inline void push( istream& ); // puts a new element in v
    void output( ostream& ); // outputs the array
};
array::array() //creat an array
{size=0;
        v=new int;
}
array::~array() //destroy an array
{
    delete[] v;
}
inline void array::swap( int a, int b )
{int aux=v[a];
    v[a]=v[b];
    v[b]=aux;
}
inline int array::getsize()
{
    return size;
}
inline bool array::check( int a, int b )
{
    return v[a] <= v[b];
}
inline bool array::check_strict( int a, int b )
{
    return v[a] < v[b];
}
inline void array::push( istream& in )
{++size;
    v=(int*)realloc( (void*)v, size*sizeof(int) );
    in>>v[size-1];
}
inline void array::output( ostream& out )
{
    for( int i=0; i < size; ++i ) out<<v[i]<<' ';
}
class HeapSort : public array
{
    void downheap( int, int );
    void make_heap( int );
public:
    HeapSort();
    ~HeapSort();
    void sortheap( int, int );
};
HeapSort::HeapSort(): array()
{
}
HeapSort::~HeapSort()
{
}
void HeapSort::downheap( int start, int end )
{
    for( int root=2*start+1; root < end; )
    {
        if( root+1 < end && check_strict( root, root+1 ) ) ++root;
        if( check( root, start ) ) return;
        swap( root, start );
        start=root;
        root=2*start+1;
    }
}
void HeapSort::make_heap( int end )
{
    for( int start=end/2-1; start >= 0; --start )
        downheap( start, end );
}
void HeapSort::sortheap( int start , int end )
{make_heap( end );
    for( end=end-1; end >= start; --end )
    {
        swap( 0, end );
        downheap( 0, end );
    }
}
class Introsort: public HeapSort
{
    int partition( int, int, int );
    inline int medianof3( int, int, int );
public:
     Introsort();
    ~Introsort();
    inline void sort( int, int, int );
};
Introsort::Introsort(): HeapSort()
{
}
Introsort::~Introsort()
{
}
int Introsort::partition( int st, int dr, int x )
{
    while( st < dr )
    {
        while(  st < dr && check_strict( st, x ) )  ++st;
        dr-=1;
        while( st < dr && check_strict( x, dr ) ) --dr;
        if( st >= dr ) return st;
        swap( st, dr );
        ++st;
    }
}
inline int Introsort::medianof3( int st, int m, int dr )
{
    if( check_strict( m, st ) )
    {
        if( check_strict( dr, m) )
            return m;
        else {
                 if( check_strict( dr, st ) )
                     return dr;
                 else return st;
             }
    }
    else  {
             if( check_strict( dr, m ) )
             {
                 if( check_strict( dr, st) )
                     return st;
                 else return dr;
             }
             else return m;
          }
}
inline void Introsort::sort( int st, int dr, int depth_limit )
{
    while( dr-st >= 0 )
    {
        if( depth_limit == 0 )
        {
            sortheap( st, dr);
            return;
        }
        --depth_limit;
        int p=partition( st, (st+dr)/2, medianof3( st, (st+dr)/2, dr-1 ) );
        sort( p, dr, depth_limit );
        dr=p;
    }
}
int main()
{int N;
    Introsort a;
    in.open(InFile);
    in>>N;
    while( N-- )
    {
        a.push( in );
    }
    a.sort( 0, a.getsize(), a.getsize() );
    out.open( OutFile );
    a.output( out );
}