How do you merge two sorted arrays into a single sorted array, and what is the complexity?
You walk through both lists with one index in each, and you always take the smaller of the two values that are in front of you.
def merge_sorted(a, b):
merged = []
i = j = 0
while i < len(a) and j < len(b):
if a[i] <= b[j]:
merged.append(a[i])
i += 1
else:
merged.append(b[j])
j += 1
# Whatever is left in one list goes at the end.
while i < len(a):
merged.append(a[i])
i += 1
while j < len(b):
merged.append(b[j])
j += 1
return merged
So why does it work? Because both lists are already in order. The smallest value that is left in the whole of the two lists is at the front of one of them or the other, so you can always take the smaller of the two fronts and be sure that you have taken the right one.
And the complexity is O of m plus n for the time, because you go through every value exactly once, and O of m plus n for the space, because the answer is a new list that holds every value.
The next question in this topic looks at the version that does not need a new list.