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>
C++ 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
std::vector<int> mergeSorted(std::vector<int> first, std::vector<int> second) {
}Worked examples
| Call | Result |
|---|---|
mergeSorted(std::vector<int>{1, 2, 4}, std::vector<int>{1, 3}) | std::vector<int>{1, 1, 2, 3, 4} |
mergeSorted(std::vector<int>{}, std::vector<int>{1, 2}) | std::vector<int>{1, 2} |
mergeSorted(std::vector<int>{1, 2}, std::vector<int>{}) | std::vector<int>{1, 2} |
mergeSorted(std::vector<int>{}, std::vector<int>{}) | std::vector<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 C++
std::vector<int> mergeSorted(std::vector<int> first, std::vector<int> second) {
std::vector<int> merged;
size_t i = 0, j = 0;
while (i < first.size() && j < second.size()) {
if (first[i] <= second[j]) merged.push_back(first[i++]);
else merged.push_back(second[j++]);
}
while (i < first.size()) merged.push_back(first[i++]);
while (j < second.size()) merged.push_back(second[j++]);
return merged;
}