Sort an Array

You are given an integer array nums. Your task is to sort the array in ascending order and return the sorted array.

The solution must satisfy the following conditions:

• Do not use any built-in sorting functions.

• The overall time complexity should be O(n log n).

• Use the minimum extra space possible.

Example 1

Input

nums = [5,2,3,1]

Output

[1,2,3,5]

Explanation

After sorting, the numbers are arranged in increasing order.

Example 2

Input

nums = [5,1,1,2,0,0]

Output

[0,0,1,1,2,5]

Explanation

The array may contain duplicate values, and they should also appear in sorted order.

Constraints

1 <= nums.length <= 5 * 10^4
-5 * 10^4 <= nums[i] <= 5 * 10^4