245. Merge Two Sorted Arrays
You are given two lists, each already in non-decreasing order. Print all their values as a single non-decreasing sequence.
Do not concatenate and sort. That throws away what you were given and costs
O((n+m) log(n+m)). Because both inputs are already ordered, the smallest
value overall is at the front of one of them, so you can produce the answer in
one pass over both.
This merge step is the second half of merge sort, and writing it here is what makes that algorithm obvious later.
Constraints - `0 ≤ n ≤ 100000` - `0 ≤ m ≤ 100000` - `1 ≤ n + m` - `-1000000000 ≤ values ≤ 1000000000`
Input
The first line contains two integers n and m.
The second line contains n integers in non-decreasing order.
The third line contains m integers in non-decreasing order.
A line is empty when its count is zero.
Output
Print the n + m values in non-decreasing order, separated by single spaces.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.