Zip two sorted lists together
Merge two sorted lists into one sorted list by always taking the smaller of the two front values. About 12 minutes.
Compare the fronts
Keep a finger on the front of each list. Compare the two values your fingers point at. The smaller one is the smallest of everything that's left, so write it down and move that finger forward one place.
Keep going until one list runs out. Then the other list's remaining values are all bigger than everything written so far, and already in order, so copy them straight on.
a, b = [1, 4], [2, 3] front = min(a[0], b[0]) # 1
Compare the fronts 2 and 1. The 1 is smaller, so it goes first.
Ties and stability
What if both fronts are equal? Take the one from the first list. It changes nothing for plain numbers, but when the values carry other information, like names, it keeps values that were equal in their original order. A sort that does this is called stable.
Using "less than or equal" for the first list is the small detail that makes the merge stable.
The fronts of the two lists are 5 and 5. Which do you take?
- AThe one from the first list, then the other next
- BNeither, because they're equal
- CBoth at the same time
Show the answer
The one from the first list, then the other next. Either gives the same numbers, but taking from the first list keeps equal values in their original order.
Merge two sorted lists
a and b are two lists of whole numbers, each already sorted from smallest to largest. Return one list containing all the values of both, sorted from smallest to largest.
a = [1, 4, 7], b = [2, 3, 9] → [1, 2, 3, 4, 7, 9]
0 ≤ length of each list ≤ 1,500 · −1,000,000 ≤ value ≤ 1,000,000