Problem

At Spotify, event scores arrive in arbitrary order and must be sorted efficiently before downstream processing. Given an array of integers nums, return a new array containing the same values sorted in ascending order.

You must solve this efficiently for large inputs. A quadratic-time approach such as comparing every pair is not acceptable for the largest cases.

Formal Specification

• Input: A list of integers nums
• Output: A new list of integers sorted in non-decreasing order
• Requirement: Do not use Python's built-in sort() or sorted()

Examples

Example 1

• Input: nums = [5, 2, 3, 1]
• Output: [1, 2, 3, 5]
• Explanation: Sorting the four values in ascending order produces [1, 2, 3, 5].

Example 2

• Input: nums = [5, 1, 1, 2, 0, 0]
• Output: [0, 0, 1, 1, 2, 5]
• Explanation: Duplicate values must be preserved, and the final order must be non-decreasing.

Constraints

• 1 <= len(nums) <= 10^5
• -10^9 <= nums[i] <= 10^9
• The solution should run in O(n log n) time or better
• Built-in sorting functions are not allowed