Write sort_numbers(nums: list[int]) -> list[int] that returns the numbers in ascending order. You may reorder nums itself or build a new list.
The point is to write the sorting yourself: don't call sorted, list.sort, heapq or any other library routine that sorts or keeps things in order for you. (The Python tests check for these calls.)
sort_numbers([5, 2, 3, 1]) # [1, 2, 3, 5]
sort_numbers([5, 1, 1, 2, 0, 0]) # [0, 0, 1, 1, 2, 5]
sort_numbers([-4, 10, -4]) # [-4, -4, 10]
sort_numbers([]) # []
Constraints: 0 <= len(nums) <= 10^5, values in [-10^9, 10^9].
The tests include large inputs that are random, already sorted, reversed, and all equal. Anything that is O(n²) on some input shape (swapping neighbours, inserting into place, or splitting around the first element) fails one of them. Aim for O(n log n) in every case.
Show hint
Two lists that are already sorted can be combined into one sorted list in a single pass, by repeatedly taking the smaller of their two front items. How could you get two sorted halves to combine?