#include <iostream>
#include <fstream>

using namespace std;

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

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

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

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

int i;
int s = 0;
int 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(int stanga, int dreapta, int *v)
{
	// cazul de baza pentru iesire din recursivitate
	if (dreapta - stanga <= 1)
		{ return; }

	// determinare intervale
	int s_start = stanga;
	int s_stop = (stanga+dreapta)/2;
	int d_start = s_stop;
	int 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()
{
    int v[10], i, n;

    f>>n;

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

    mergesort(0, n, v);

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

    return 0;

}