/* 
 * File:   main.cpp
 * Author: speedemon
 *
 * Created on October 7, 2009, 3:04 PM
 */
#include <cmath>
#include <vector>
#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=v[i];
    v[i]=v[j];
    v[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 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( r, 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( s, e );
        downheap( s, e );
    }
}
void IntroSort::QSort( unsigned s, unsigned e )
{
    vector<unsigned> left, right;
    unsigned lf, rh, l1, l2, r1, r2, x;
    left.push_back(s); right.push_back(e);
    while( !left.empty() )
    {
        lf=left.front(); rh=right.front()-1;
        if( lf < rh )
        {
            x=v[lf];
            while( lf < rh )
            {
                while( lf < rh && x <= v[rh] )
                    --rh;
                if( lf < rh )
                    v[lf]=v[rh],++lf;
                else break;
                while( lf < rh && v[lf] <= x )
                    --lf;
                if( lf < rh )
                    v[rh]=v[lf],--rh;
                else break;
            }
            v[lf]=x;
            s=right.size()-2;
            left.push_back(lf+1); right.push_back(right.front());
            right[s]=lf;
            if( right.back()-left.back() > right[s]-left[s] )
            {
                l1=left.back(); left.pop_back(); l2=left.back(); left.pop_back();
                r1=right.back(); right.pop_back(); r2=right.back(); right.pop_back();
                left.push_back(l2); left.push_back(l1);
                right.push_back(r2); right.push_back(r1);
            }
        }
        else left.pop_back(),right.pop_back();
    }
}
inline void IntroSort::sort()
{
    HeapSort( 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;
}