/* 
 * 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( int, int );
    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( int s, int e )
{
    if( s >= e )
        return;
    unsigned x=v[e];
    int i=s-1,j;
    for( j=s; j < e; ++j )
        if( v[j] <= x )
        {
            ++i;
            swap( v[i], v[j] );
        }
    ++i;
    swap( v[i], v[e] );
    QSort( s, i-1 );
    QSort( i+1, e );

}
inline void IntroSort::sort()
{
    QSort( 0, size-1 );
}
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;
}