/* 
 * File:   main.cpp
 * Author: speedemon
 *
 * Created on October 7, 2009, 3:04 PM
 */
#include <cmath>
#include <queue>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>

/*
 *
 */

using namespace std;
ifstream in;
ofstream out;
class IntroSort
{
    unsigned *v;
    unsigned size;
    inline void swap( unsigned&, unsigned& );
    inline unsigned medianof3( unsigned, unsigned, unsigned );
    void downheap( unsigned, unsigned );
    void HeapSort( unsigned, unsigned );
    void QSort( unsigned, unsigned );
    inline void SortIntro( unsigned, unsigned );
public:
    IntroSort(); //create an object
    ~IntroSort(); //destroy the object
    inline void push( istream& ); // put a new element
    inline void output( ostream& ); //output the array
    inline void sort();   //using one of the three methods sorts the elements
};
IntroSort::IntroSort() //constructor
{size=0; //there are no elements in the array
    v=new unsigned; // alloc memory
}
IntroSort::~IntroSort() //deconstructor
{
    delete[] v; //delete the array
}
inline void IntroSort::push( istream& in ) //put a new element
{++size;
    v=(unsigned*)realloc( (void*)v, size*sizeof(unsigned) ); //realloc the memory for a new element
    in>>v[size-1];
}
inline void IntroSort::output( ostream& out ) //output the array
{
    copy( v, v+size, ostream_iterator<unsigned>( out, " " ) );
}
inline void IntroSort::swap( unsigned& i, unsigned& j ) //swaps the elments v[i] and v[j]
{unsigned aux=i;
    i=j;
    j=aux;
}
/* Median 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 unsigned IntroSort::medianof3( unsigned a, unsigned b, unsigned c )
{
    if( v[a] > v[b] )
    {
        if( v[b] > v[c] )
            return b;
        else if( v[a] > v[c] )
               return c;
        return a;
    }
    else if( v[b] > v[c] )
         {
              if( v[a] > v[c] )
                  return a;
              else return c;
         }
    return b;
}
inline void IntroSort::downheap( unsigned s, unsigned e )
{unsigned r=2*s+1;
    while( r < e )
    {
        if( r+1 < e && v[r] < v[r+1] ) ++r;
        if( v[r] <= v[s] ) return; //has heap structure
        swap( v[r], v[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 ); //creat a  heap from the arrat v
    downheap( s, e );
    for( e=e-1; e > s; --e )
    {
        swap( v[s], v[e] );
        downheap( s, e );
    }
}
void IntroSort::QSort( unsigned s, unsigned e )
{
    int i=0,lf,rh;
    unsigned *left, *right, x, Index;
    left= new unsigned[e/2];
    right= new unsigned[e/2];
    left[0]=s; right[0]=e;
    while( i >= 0 )
    {
        lf=left[i]; rh=right[i]-1;
        if( lf < rh )
        {//Index=medianof3( lf, lf+(rh-lf)/2, rh );
            x=v[lf];
            while( lf < rh )
            {
                while( lf < rh && x <= v[rh] )
                    --rh;
                if( lf < rh )
                    v[lf++]=v[rh];
                else break;
                while( lf < rh &&  v[lf] <= x )
                    ++lf;
                if( lf < rh )
                    v[rh--]=v[lf];
                else break;
            }
            v[lf]=x;
            left[i+1]=lf+1; right[i+1]=right[i]; right[i++]=lf;
            if( right[i] - left[i] > right[i-1]-left[i-1] )
            {
                swap( right[i], right[i-1] );
                swap( left[i], left[i-1] );
            }
        }
        else --i;
    }
    delete[] left;
    delete[] right;
}
inline void IntroSort::sort()
{
    QSort( 0, size );
}
int main()
{int N;
 IntroSort a; //create the object a
    in.open("algsort.in");
    in>>N;
    while( N-- )
    {
        a.push(in);
    }
    out.open("algsort.out");
    a.sort();
    a.output(out);
    return EXIT_SUCCESS;
}