Combine two sorted lists into one sorted list, without sorting.
What to build
The merge step that lies at the heart of merge sort, one of the fastest ways to sort a list.
Requirements
- Read two lines, each a list of numbers in increasing order.
- Print one list holding every number, in increasing order, separated by single spaces.
- Solve it by walking along the two lists. Do not call
sort.
Input
Two lines of whole numbers separated by single spaces.
Output
One line.
Constraints
Each list has from 1 to 200 numbers, already in increasing order. Numbers can repeat.
Example
Input:
1 4 9
2 3 10
Output:
1 2 3 4 9 10
Why it works
The smallest item left must be at the front of one of the two lists, so comparing two items is enough at each step. Each item is looked at once, which makes this much faster than sorting again.
Examples
Example 1 · Input
1 4 9 2 3 10
Expected output
1 2 3 4 9 10
Example 2 · Input
5 1 2 3
Expected output
1 2 3 5
Hints
Hint 1
Keep one index for each list, both starting at 0.
Hint 2
Compare the two current items, take the smaller one and move that index forward.
Hint 3
When one list runs out, add everything left in the other.
Solution
Show one correct solution (try it yourself first)
const a = prompt().split(" ").map(Number);
const b = prompt().split(" ").map(Number);
const merged = [];
let i = 0;
let j = 0;
while (i < a.length && j < b.length) {
if (a[i] <= b[j]) {
merged.push(a[i]);
i++;
} else {
merged.push(b[j]);
j++;
}
}
console.log([...merged, ...a.slice(i), ...b.slice(j)].join(" "));