Sort a list with merge sort
You get a list of integers nums. Put the same numbers in order from smallest to largest and return that list. Every copy of a repeated number stays: [2, 1, 2] becomes [1, 2, 2].
Write the sort yourself: no sorted, no list.sort, and no heapq or bisect helpers. It must run in O(n log n) time, where n is the length of the list and log n is how many times n can be halved before it reaches 1. You may return a new list, or nums itself rearranged.
nums = [7, 2, 9, 4]Output[2, 4, 7, 9]Split into [7, 2] and [9, 4], sort each half to get [2, 7] and [4, 9], then merge the two halves.
nums = [3, -2, 3, 0, -2]Output[-2, -2, 0, 3, 3]Negative numbers are fine, and both copies of 3 and of -2 stay.
0 ≤ len(nums) ≤ 5 × 104
-5 × 104 ≤ nums[i] ≤ 5 × 104
No
sorted, nolist.sort, noheapqorbisect.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.