T588262 归并排序

归并排序（Merge Sort）采用“**分治：分 → 治 → 合并**”的思想：把序列拆成两半，分别用归并排序排好序，再用**有序归并**把两个有序段合成一个有序段。 * **稳定性**：**稳定**。在归并时，若左右元素相等，**先取左段**即可保持相对次序。 * **时间复杂度**：最好 / 平均 / 最坏均为 $O(n\log n)$。 * **空间复杂度**：$O(n)$ 额外空间（用于临时缓冲区）。 

给定 $n$ 个整数，请用**归并排序**按**升序**排序并输出。

* 第一行：一个整数 $n$。 * 第二行：$n$ 个整数（32 位有符号范围内）。

输出一行，将这 $n$ 个数按升序排列，数之间以一个空格分隔、。

* 数据范围：$1 \le n \le 100000$。