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
public List<int> MergeSorted(List<int> first, List<int> second) {
}Worked examples
| Call | Result |
|---|---|
MergeSorted(new List<int> { 1, 2, 4 }, new List<int> { 1, 3 }) | new List<int> { 1, 1, 2, 3, 4 } |
MergeSorted(new List<int> { }, new List<int> { 1, 2 }) | new List<int> { 1, 2 } |
MergeSorted(new List<int> { 1, 2 }, new List<int> { }) | new List<int> { 1, 2 } |
MergeSorted(new List<int> { }, new List<int> { }) | new List<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#
public List<int> MergeSorted(List<int> first, List<int> second) {
var merged = new List<int>();
int i = 0, j = 0;
while (i < first.Count && j < second.Count) {
if (first[i] <= second[j]) merged.Add(first[i++]);
else merged.Add(second[j++]);
}
while (i < first.Count) merged.Add(first[i++]);
while (j < second.Count) merged.Add(second[j++]);
return merged;
}