Merge two sorted queues
A worker pulls from two queues that are each already sorted, and must hand downstream one combined sorted stream.
- Each input is already sorted ascending.
- The result merges them ascending, and equal values from both queues both survive.
- An empty queue on either side is fine; the other side comes through whole.
merge_sorted(first: list<int>, second: list<int>) → list<int>
Where you start
def merge_sorted(first: list[int], second: list[int]) -> list[int]:
Worked examples
| Call | Result |
|---|---|
merge_sorted([1, 2, 4], [1, 3]) | [1, 1, 2, 3, 4] |
merge_sorted([], [1, 2]) | [1, 2] |
merge_sorted([1, 2], []) | [1, 2] |
merge_sorted([], []) | [] |
Hint
Two pointers, one for each list. Take the smaller head, advance that pointer, and when one side runs out the rest of the other side follows.
Reference solution in Python
def merge_sorted(first: list[int], second: list[int]) -> list[int]:
merged = []
i = j = 0
while i < len(first) and j < len(second):
if first[i] <= second[j]:
merged.append(first[i])
i += 1
else:
merged.append(second[j])
j += 1
merged.extend(first[i:])
merged.extend(second[j:])
return merged