Merge sort is the classic divide and conquer sorting algorithm: split the list in half, sort each half, then merge the two sorted halves. Every level of splitting does O(n) merging work, and there are only O(log n) levels, giving O(n log n) overall.
Given a list of integers nums, return a new list containing the same elements in non-decreasing order. Implement merge sort yourself.
Examples
Input: nums = [5, 2, 3, 1]
Output: [1, 2, 3, 5]
Input: nums = [5, 1, 1, 2, 0, 0]
Output: [0, 0, 1, 1, 2, 5]
Constraints
0 <= len(nums) <= 5000- Do not call
sorted()orlist.sort(); the point is to build the algorithm. - Aim for O(n log n) time.
Goals
- Split a problem in half, solve each half recursively, and combine the results
- Reuse the two-pointer merge step on the two sorted halves
- Explain why the algorithm runs in O(n log n) time