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.
mergeSorted(first: list<int>, second: list<int>) → list<int>
Go needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
func mergeSorted(first []int, second []int) []int {
}Worked examples
| Call | Result |
|---|---|
mergeSorted([]int{1, 2, 4}, []int{1, 3}) | []int{1, 1, 2, 3, 4} |
mergeSorted([]int{}, []int{1, 2}) | []int{1, 2} |
mergeSorted([]int{1, 2}, []int{}) | []int{1, 2} |
mergeSorted([]int{}, []int{}) | []int{} |
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 Go
func mergeSorted(first []int, second []int) []int {
merged := []int{}
i, j := 0, 0
for i < len(first) && j < len(second) {
if first[i] <= second[j] {
merged = append(merged, first[i])
i++
} else {
merged = append(merged, second[j])
j++
}
}
merged = append(merged, first[i:]...)
merged = append(merged, second[j:]...)
return merged
}