Given an array of nums, sort it using a general-purpose sorting algorithm.
You must solve it without using any built-in sorting functions and in O(n log n) time complexity with the smallest space complexity possible.
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 * 104-5 * 104 <= nums[i] <= 5 * 104