#include <cmath>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>

using namespace std;
ifstream in;
ofstream out;
class IntroSort
{
	int *v;
	unsigned size;
	inline void swap( unsigned, unsigned ); 
	inline int medianof3( unsigned, unsigned, unsigned );
	unsigned partition( unsigned, unsigned, int );
	void downheap( unsigned, unsigned );
    void HeapSort( unsigned, unsigned );
	inline void introsort( unsigned, unsigned, unsigned );
	void InsertionSort( unsigned, unsigned );
public:
 	IntroSort();
	~IntroSort();
	inline void push( istream& );
	inline void output( ostream& );
	inline void sort( unsigned, unsigned );
};
IntroSort::IntroSort()
{size=0;
	v=new int;
}
IntroSort::~IntroSort()
{
	delete[] v;
}
inline void IntroSort::push( istream& in )
{++size;
	v=(int*)realloc( (void*)v, size*sizeof( int ) );
	in>>v[size-1];
}
inline void IntroSort::output( ostream& out )
{
	copy( v, v+size, ostream_iterator< int >( out, " " ) );
}
inline void IntroSort::swap( unsigned a, unsigned b )
{int aux=v[a];
	v[a]=v[b];
	v[b]=aux;
}
inline void IntroSort::downheap( unsigned s, unsigned e )
{
	for( unsigned r=2*s+1; r < e; )
	{
		if( r+1 < e && v[r] < v[r+1] ) ++r;
		if( v[r] <= v[s] ) return;
		swap( r, s );
        s=r;
		r=2*s+1;
	}
}
inline void IntroSort::HeapSort( unsigned s, unsigned e )
{
	for( unsigned w=e/2-1; w > s; --w )
		downheap( w, e );
	downheap( s, e );
	for( e-=1; e > s; --e )
	{
		swap( s, e );
		downheap( s, e );
	}
	swap( s, e );
	downheap( s, e );
}
/*              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 int 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( unsigned st, unsigned dr, int x )
{
	while( st < dr )
	{
		while( st < dr && v[st] <= x ) ++st;
		--dr;
		while( st < dr && x <= v[dr] ) --dr;
		if( !( st < dr ) )
			return st;
		swap( st, dr );
		++st;
	}
	return st;
}
inline void IntroSort::introsort( unsigned st, unsigned dr, unsigned depth_limit )
{
	while( st < dr )
	{
		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;
	int 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;
    }
}
inline void IntroSort::sort( unsigned st, unsigned dr )
{
	introsort( st, dr, 2*(unsigned)log((double)dr)/log((double)2) );
	InsertionSort( st, dr );
}
int main()
{unsigned N,i;
 IntroSort a; 
	in.open("algsort.in");
	in>>N;
	for( i=0; i < N; ++i ) a.push( in );
	a.sort( 0, N );
	out.open("algsort.out");
	a.output( out );
	return EXIT_SUCCESS;
}