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


/*
 * 
 */

using namespace std;
ifstream in;
ofstream out;
int *v;
/**  Heap Sort  **/
inline void swap( int& a, int& b )
{
    a+=b;
    b=a-b;
    a-=b;
}
void downheap( int start, int end )
{
    for( int root=2*start+1; root < end; )
    {
        if( root+1 < end && v[root] < v[root+1] ) ++root;
        if( v[root] <= v[start] ) return;
        swap( v[root], v[start] );
        start=root;
        root=2*start+1;
    }
}
void HeapSort( int start, int end )
{
    for( int w=end/2-1; w >= 0; -- w ) //make a heap from v
        downheap( w, end );
    for( end=end-1; end > start; --end )
    {
        swap( v[0], v[end] );
        downheap( 0, end );
    }
}
/** Introsort **/
int partition( int st, int dr, int x )
{
    while( st < dr )
    {
        while( st < dr && v[st] < v[x] ) ++st;
        --dr;
        while( st < dr && v[x] < v[dr] ) --dr;
        if( st >= dr )
            return st;
        swap( st, dr );
        ++st;
    }
}/* Medina of 3
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 medianof3( int a, int b, int c )
{
    if( a > b )
    {
        if( b > c )
            return b;
        else if( a > c )
                return c;
        return a;
    }
    else if( b > c )
        {
            if( a > c )
                return a;
            else return c;
        }
    return b;
}
inline void IntroSort( int st, int dr, int depth_limit )
{
    while( dr - st >= 0 )
    {
        if( !depth_limit )
        {
            HeapSort( st, dr );
            return;
        }
        --depth_limit;
        int p=partition( st, dr, medianof3( v[st], v[st+(dr-st)/2], v[dr-1] ) );
        IntroSort( p, dr, depth_limit );
        dr=p;
    }
}
int main()
{int N,i;
    in.open(InFile);
    in>>N;
    v=new int[N];
    for( i=0; i < N; ++i ) in>>v[i];
    IntroSort( 0, N, 2*log(N)/log(2) );
    out.open(OutFile);
    for( i=0; i < N; ++i ) out<<v[i]<<' ';
    delete[] v;
    return EXIT_SUCCESS;
}