问题描述

给你一个整数数组，请你将该数组升序排序。

你必须在不使用任何内置函数的情况下解决问题，要求：

• 时间复杂度为 O(n log n)
• 空间复杂度尽可能小

格式

输入

• 一个整数数组，包含 n 个元素。

输出

• 一个升序排列的整数数组。

样例

样例1

输入

4
5 2 3 1

输出

1 2 3 5

样例2

输入

6
5 1 1 2 0 0

输出

0 0 1 1 2 5

提示

• 1 <= n <= 5 × 10⁴
• -5 × 10⁴ <= 数组中的整数 <= 5 × 10⁴