Merge Two Sorted Arrays
Easy · rating 1000 · arrays, sorting
Read two lines, each a (possibly empty) list of space-separated integers already sorted ascending. Print the merged result, sorted ascending, space-separated.
Editorial
Approach
Both inputs are already sorted, so walk them with two pointers, always taking the smaller current element — this is the merge step of merge sort. When one list runs out, append the remainder of the other.
i = j = 0; out = []
while i < len(a) and j < len(b):
if a[i] <= b[j]: out.append(a[i]); i += 1
else: out.append(b[j]); j += 1
out += a[i:] + b[j:]Complexity
Time: O(n + m). Space: O(n + m) for the output.