Easy Two Pointers Sorting
In plain English: Combine two sorted arrays into one — the merge step that powers merge sort.
The merge step is the workhorse of merge sort — two pointers always pick the smaller remaining element.
Prompt
Merge two sorted arrays into one sorted array. (Speed drill — same as #6.)
Try to write it from scratch before scrolling down.
Solution
def merge(a, b):
res, i, j = [], 0, 0
while i < len(a) and j < len(b):
if a[i] <= b[j]:
res.append(a[i]); i += 1
else:
res.append(b[j]); j += 1
res.extend(a[i:])
res.extend(b[j:])
return res
# Test: merge([1,3,5,7], [2,4,6,8]) == [1,2,3,4,5,6,7,8]