#include <fstream>
#include <vector>
const int max_n = 500000;
void merge(std::vector<int>& v, int left, int m, int right)
{
static std::vector<int> tmp(max_n);
int i = m + 1;
int j = left;
int k = 0;
while (j <= m && i <= right)
{
if (v[j] < v[i])
{
tmp[k] = v[j];
++j;
}
else
{
tmp[k] = v[i];
++i;
}
++k;
}
for (; j <= m; ++j)
{
tmp[k++] = v[j];
}
for (; i <= right; ++i)
{
tmp[k++] = v[i];
}
std::copy(tmp.begin(), tmp.begin() + k, v.begin() + left);
}
void sort(std::vector<int>& v, int left, int right)
{
if (left >= right)
return;
int m = (left + right) >> 1;
sort(v, left, m);
sort(v, m + 1, right);
merge(v, left, m, right);
}
int main()
{
int n;
std::vector<int> v;
std::ifstream in("algsort.in");
in >> n;
v.resize(n);
for (int i = 0; i < n; ++i)
{
in >> v[i];
}
sort(v, 0, n - 1);
std::ofstream out("algsort.out");
for (int i = 0; i < n; ++i)
{
out << v[i] << ' ';
}
return 0;
}