Merge two sorted lists
One pointer in each list; take the smaller. About 10 minutes.
Two sorted queues, one line
Two queues of people, each already sorted by height, need to merge into one sorted line. You'd look at the front of each queue, send the shorter person forward, and repeat.
That's exactly how to merge two sorted arrays. Give each array its own finger, both starting at the front. The smallest value not yet used is always under one of the two fingers. Take the smaller, and move that finger along.
1 vs 2: take 1 from a. Result [1]. i moves on.
When one queue runs out
Stop comparing as soon as one array is used up. The other may still have values left. They're all bigger than everything you've taken, and already in order, so tack them onto the end as they are.
Forgetting the leftovers is the most common bug in this problem, and it only shows up when the two arrays have different largest values.
i = j = 0
result = []
while i < len(a) and j < len(b):
if a[i] <= b[j]:
result.append(a[i])
i += 1
else:
result.append(b[j])
j += 1
return result + a[i:] + b[j:]Merging 2, 5 with 3, 4, 9: the result so far is 2, 3, 4. The fingers are on 5 and on 9. What happens next?
- ATake 5
- BTake 9
- CStop: the answer is 2, 3, 4
Show the answer
Take 5. 5 is smaller than 9, so it goes next. Then the first array is used up and 9 is copied on the end.
Merge two sorted lists
You get two lists, a and b, each sorted from smallest to largest. Return one list with every value from both, sorted from smallest to largest. Keep repeated values. Try it without sorting.
a = [1, 4, 7], b = [2, 3, 8] → [1, 2, 3, 4, 7, 8]
0 ≤ length of a, length of b ≤ 10,000 · both sorted ascending