/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on May 13, 2010, 4:05 PM
 */
#include <vector>
#include <cstdlib>
#include <fstream>
#include <iterator>

/*
 * 
 */
using namespace std;
vector< int > v;
inline int medianof3( int x, int y, int z )
{
    int xx=v[x], yy=v[y], zz=v[z];
    int a=max( xx, max( yy, zz ) ), b, c=min( xx, min( yy, zz ) );
    if( a == xx )
    {
        if( c == yy )
            b=zz;
        else b=yy;
    }
    else if( a == yy )
         {
             if( c == xx )
                 b=zz;
             else b=xx;
         }
         else {
                  if( c == xx )
                      b=yy;
                  else b=xx;
              }
    v[x]=c; v[y]=b; v[z]=a;
    return y;
}
inline void QSort( int left, int right )
{
    if( left < right )
    {
        int lleft=left-1, rright=right+1, pValue=v[ medianof3( left, left+(right-left)/2, right ) ];
        for( ; ; )
        {
            while( pValue > v[++lleft] );
            while( pValue < v[--rright] );
            if( lleft > rright )
                break;
            swap( v[lleft], v[rright] );
        }
        if( left < rright )
            QSort( left, rright );
        if( lleft < right )
            QSort( lleft, right );
    }
}
int main(int argc, char** argv)
{
    int N;
    ifstream in( "algsort.in" );
    in>>N;
    copy( istream_iterator<int>(in), istream_iterator<int>(), back_inserter(v) );
    ofstream out( "algsort.out" );
    QSort( 0, N-1 );
    copy( v.begin(), v.end(), ostream_iterator<int>( out, " " ) );
    out<<'\n';
    return (EXIT_SUCCESS);
}