#include <ctime>
#include <vector>
#include <cstdlib>
#include <fstream>
#include <iterator>
#include <algorithm>

using namespace std;

vector<int> v;

inline void _swap(int& x, int& y) {int aux = x; x = y; y = aux;}
int partition(int left, int right, int pIndex)
{
    int pValue, i, j;

    pValue = v[pIndex];
    _swap(v[left], v[pIndex]);
    
    for(i = left, j = right + 1; true; )
    {
	while(v[--j] > pValue);
        while(i <= right && v[++i] < pValue);

        if(i >= j) break;
        _swap(v[i], v[j]);
    }
    
    _swap(v[left], v[j]);

    return j;
}

inline int medianOfThree(int left, int middle, int right)
{
    if(v[left] > v[middle])
    {
	if(v[middle] > v[right])    return middle;
        else if(v[left] < v[right]) return left;
        else                        return right;
	     
    }    
    else {
	     if(v[middle] < v[right])    return middle;
             else if(v[left] > v[right]) return left;
	     else                        return right;
         }
}

inline void QuickSort(int left, int right)
{
    if(left >= right) return;
    if(9 >= right - left)
    {
        for(int i = left; i < right; ++i)
	{
	    for(int j = i + 1; j <= right; ++j)
	    {
		if(v[i] > v[j])
		{
		    _swap(v[i], v[j]);
		}
	    }
	}
        return;
    } 
   
   
    _swap(v[left], v[rand() % (right - left + 1) + left]);
    
    int pIndex = partition(left, right, medianOfThree(left, (left + right) >> 1, right));

    QuickSort(left, pIndex - 1);
    QuickSort(pIndex + 1, right);
}

int main()
{
    int N;
    ifstream in("algsort.in");
    ofstream out("algsort.out");

    in >> N;
    copy(istream_iterator<int>(in), istream_iterator<int>(), back_inserter(v));

    srand(time(NULL));
    QuickSort(0, v.size() - 1);
    copy(v.begin(), v.end(), ostream_iterator<int>(out, " "));
    out << '\n';

    return EXIT_SUCCESS;
}