/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on December 31, 2009, 4:23 PM
 */
#include <vector>
#include <fstream>
#include <iterator>

/*
 *
 */
using namespace std;
vector<int> v;
int size_threshold;
ofstream out;
inline void swap( int x, int y )
{
    v[x]+=v[y];
    v[y]=v[x]-v[y];
    v[x]-=v[y];
}
inline int medianof3( int left, int middle, int right )
{
    if( v[left] > v[middle] )
        swap( left, middle );
    if( v[left] > v[right] )
        swap( left, right );
    if( v[middle] > v[right] )
        swap( middle, right );
    swap( middle, right-1 );
    return v[right-1];
}
int Partition( int left, int right, int pValue )
{
    int leftPtr=left, rightPtr=right;
    while( true )
    {
        while( v[++leftPtr] < pValue );
        while( v[--rightPtr] > pValue );
        if( leftPtr >= rightPtr )
            break;
        swap( leftPtr, rightPtr );
    }
    swap( left, right-1 );
    return leftPtr;
}
void QSort_Loop( int left, int right )
{
    while( right-left > size_threshold )
    {
        int p=Partition( left, right, medianof3( left, left+(right-left)/2-1, right-1 ) );
        if( p-left >= p-right )
        {
            QSort_Loop( p, right );
            right=p-1;
        }
        else {
                QSort_Loop( left, p );
                left=p+1;
             }
    }
}
void Insertion_Sort( int left, int right )
{int key, j;
    for( left+=1; left < right; ++left )
    {
        key=v[left];
        for( j=left-1; j >=0 && v[j] > key; --j )
            v[j+1]=v[j];
        v[j+1]=key;
    }
}
inline void QSort( int left, int right )
{
    QSort_Loop( left, right );
    Insertion_Sort( left, right );
}
int Log2( int n)
{
  int pos = 0;
  if (n >= 1<<16) { n >>= 16; pos += 16; }
  if (n >= 1<< 8) { n >>=  8; pos +=  8; }
  if (n >= 1<< 4) { n >>=  4; pos +=  4; }
  if (n >= 1<< 2) { n >>=  2; pos +=  2; }
  if (n >= 1<< 1) {           pos +=  1; }
  return ((n == 0) ? (-1) : pos);
}
int main()
{int n;
    ifstream in("algsort.in");
    in>>n;
    copy( istream_iterator<int>(in), istream_iterator<int>(), back_inserter(v) );
    out.open("algsort.out");
    size_threshold=Log2(n);
    QSort( 0, n );
    copy( v.begin(), v.end(), ostream_iterator<int>(out, " ") );
    return 0;
}