/**
* @author lesifh
* @description 归并排序
* 算法思想:以整个区间的最中间来分,分成左边和右边
* 先递归两边,再进行排序
* 1.确定分界点 mid = (l + r) / 2 下标值(位置)
* 2.递归排序左边和右边(排序后左右两边会变成两个有序序列)
* 3.归并 将两个有序的数组合二为一(双指针算法,也是归并算法的难点)
* 每次归并的时间复杂度:O(n)
* 归并排序时间复杂度:O(nlogn)
* */
var buf = ''
process.stdin.on('readable', function () {
const chunk = process.stdin.read();
if (chunk) buf += chunk.toString(); else return ;
});
const getArr = str => str.split('\n')[1].split(' ')
.filter(e => e)
.map(Number);
let tmp = [];
function mergeSort(q, l , r) {
if (l >= r) return;
const mid = l + r >> 1;
mergeSort(q, l, mid), mergeSort(q, mid + 1, r);
let k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
if (q[i] <= q[j]) tmp[k ++] = q[i ++];
else tmp[k ++] = q[j ++];
while (i <= mid) tmp[k ++] = q[i ++];
while (j <= r) tmp[k ++] = q[j ++];
for (i = l, j = 0; i <= r; i ++, j ++) q[i] = tmp[j];
}
process.stdin.on('end', function () {
// 获得输入完毕后的数组
const arr = getArr(buf)
// 对数组运行函数
mergeSort(arr, 0, arr.length - 1);
// 遍历输出数组
arr.forEach(item => process.stdout.write(item + ' '))
});