#include <fstream>
#include <iostream>	
#include <stdlib.h>
using namespace std;

int* merge( int* left, int leftSize, int* right, int rightSize )
{
	int leftIndex = 0;
	int rightIndex = 0;
	int* res = (int*) malloc( ( leftSize + rightSize ) * sizeof( int ) );
	while( leftIndex < leftSize && rightIndex < rightSize )
		if( *( left + leftIndex ) < *( right + rightIndex ) ) 
			*( res + leftIndex + rightIndex ) = *( left + leftIndex++ );
		else
			*( res + leftIndex + rightIndex ) = *( right + rightIndex++ );
	while( leftIndex < leftSize )
		*( res + leftIndex + rightIndex ) = *( left + leftIndex++ );
	while( rightIndex < rightSize ) 
		*( res + leftIndex + rightIndex ) = *( right + rightIndex++ );
	return res;
}

int* mergesort( int* toSort, int size )
{
	if( size < 2 )
		return toSort;
	int* left = mergesort( toSort, size / 2 );
	int* right = mergesort( toSort + size / 2, size - size / 2 );
	return merge( left, size / 2, right, size - size / 2 );	
}

void deliver( int* res, int size )
{
	ofstream out( "algsort.out" );
	for( int i = 0; i < size; ++ i )
		out << *( res + i ) << '\n';
}

int main( )
{
	ifstream in( "algsort.in" );
	int size;
	in >> size;
	int* toSort = (int*) malloc( size * sizeof( int ) );
	for( int i = 0; i < size; ++i )
		in >> *( toSort + i );
	deliver( mergesort( toSort, size ), size );
	return 0;
}