/* 
 * 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 )
{int aux=a;
    a=b;
    b=aux;
}
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] <= x ) ++st;
        --dr;
        while( st < dr && x <= v[dr] ) --dr;
        if( st >= dr  )
            return st;
        swap( v[st], v[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( 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];
        }
        else  return v[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( st, st+(dr-st)/2+1, 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];
    out.open(OutFile);
    IntroSort( 0, N, 2*log(N)/log(2) );
    for( i=0; i < N; ++i ) out<<v[i]<<' ';
    delete[] v;
    return EXIT_SUCCESS;
}