Sort Array

Given an array of integers nums, implement your own sorting algorithm to sort it in ascending order without calling a built-in sort function.

Your solution should run in O(n log n) time on average.

Example 1

Input: nums = [5, 2, 3, 1]
Output: [1, 2, 3, 5]

Example 2

Input: nums = [5, 1, 1, 2, 0, 0]
Output: [0, 0, 1, 1, 2, 5]

Constraints

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