Challenge
Two arrays are already sorted in nondecreasing order. Merge them into one nondecreasing list, retaining every occurrence of duplicate values. Aim to use the existing order instead of sorting the concatenation.
Input and output contract
Combined length ≤ 5,000; integer elements between -1,000,000 and 1,000,000. Either or both lists may be empty.
All tests follow this contract. You do not need to validate malformed input. Return the requested result from merge_sorted_arrays; printed output is not your answer. Standard-library tools are allowed. Implement your solution in Python 3.12.
Target complexity: O(n + m) time and output space
Return values are checked by type. Use the exact function name. Print output is not your answer. Tests have time and memory limits.
Public examples
Arguments
[[1, 3, 3], [2, 3, 4]]
Expected return
[1, 2, 3, 3, 3, 4]
Arguments
[[], [-3, 0]]
Expected return
[-3, 0]
Arguments
[[2, 2], [2]]
Expected return
[2, 2, 2]
Hint
Compare the first item not yet used from each list, then advance only its pointer.
The worked solution unlocks after completion, or with Premium access.