Split, sort the halves, merge
Sort a list by splitting it in two, sorting each half the same way, and merging the results. About 15 minutes.
Trust the smaller sorts
Here's the whole idea. To sort a list, cut it in half. Sort the left half, sort the right half, and merge the two sorted halves into one. You already know how to merge.
How do you sort each half? The same way, by cutting it in half again. You keep cutting until each piece has just one value, and a single value is already sorted. Then the merges build the answer back up, one level at a time.
mid = len(nums) // 2 left = nums[:mid] right = nums[mid:]
Start with the whole list. Cut it in half: [8, 3] and [6, 1, 4].
Why n times log n
Look at the levels. The top level merges one list of n values. The next has two lists of n over 2, together still n values. The one after that has four lists, still n values in total. Each level costs about n, and halving n down to 1 takes log n levels.
So total work is n times log n, always. Even a reversed list takes the same, because the splits don't depend on the values.
A list has 1,000 values. Roughly how many levels of splitting does merge sort do?
- AAbout 10, since halving 1,000 reaches 1 after about 10 steps
- B1,000, one per value
- C2, one split and one merge
Show the answer
About 10, since halving 1,000 reaches 1 after about 10 steps. Each split halves the pieces, and 2 to the power of 10 is about 1,000.
Merge sort
nums is a list of whole numbers. Return the list sorted from smallest to largest. Use the split, sort the halves, merge idea.
nums = [5, 2, 4, 1, 3] → [1, 2, 3, 4, 5]
0 ≤ length ≤ 3,000 · −1,000,000 ≤ value ≤ 1,000,000