#include <iostream>
#include <fstream>

using namespace std;

ifstream f("algsort.in");
ofstream g("algsort.out");

void interclasare(uint32_t *v, uint32_t s_start, uint32_t s_stop, uint32_t d_start, uint32_t d_stop)
{

// dimensiunile initiale ale celor 2 subvectori
uint32_t s_lungime = s_stop - s_start;
uint32_t d_lungime = d_stop - d_start;

// elementele initiale date spre comparare
uint32_t s_jumatate[s_lungime];
uint32_t d_jumatate[d_lungime];

uint32_t i;
uint32_t s = 0;
uint32_t d = 0;

// copierea valorilor in subvectorii temporali
for (i = s_start; i < s_stop; i++, s++)
	{
	 s_jumatate[s] = v[i];
	}

for (i = d_start; i < d_stop; i++, d++)
	{
	 d_jumatate[d] = v[i];
	}

// asezarea valorilor pe pozitiile corespunzatoare
for (i = s_start, s = 0, d = 0; s < s_lungime && d < d_lungime; i++)
{
if (s_jumatate[s] < d_jumatate[d])
		{
		v[i] = s_jumatate[s];
		s++;
		}
	else
		{
		v[i] = d_jumatate[d];
		d++;
		}

}

// completarea cu restul valorilor ramase
for ( ; s < s_lungime; i++, s++)
	v[i] = s_jumatate[s];

for( ; d < d_lungime; i++, d++)
	v[i] = d_jumatate[d];

}


void mergesort(uint32_t stanga, uint32_t dreapta, uint32_t *v)
{
	// cazul de baza pentru iesire din recursivitate
	if (dreapta - stanga <= 1)
		{ return; }

	// determinare intervale
	uint32_t s_start = stanga;
	uint32_t s_stop = (stanga+dreapta)/2;
	uint32_t d_start = s_stop;
	uint32_t d_stop = dreapta;

	// apel recursiv pe partea stanga
	mergesort(s_start, s_stop, v);

	// apel recursiv pe partea dreapta
	mergesort(d_start, d_stop, v);

	// interclasam cele 2 jumatati
	interclasare(v, s_start, s_stop, d_start, d_stop);
}

int main()
{
    uint32_t i, n;

    f>>n;

    uint32_t v[n+1];

    for(i=0; i<n; i++)
        f>>v[i];

    mergesort(0, n, v);

    for(i=0; i<n; i++)
        g<<v[i]<<" ";

    //cout<<sizeof(uint32_t);

    return 0;

}