Loops, Sorting
This ends up being a merge — you can loop and look at the first item in both A and B. Whichever should get sorted first goes onto the sorted list. This is very similar to the merge stage of merge sort.
The runtime for this is O(a + b), where a and b are the lengths of lists a and b, respectively.
def sort_ab(a, b):
"""Given already-sorted lists, `a` and `b`, return sorted list of both.
You may not use sorted() or .sort().
"""
# START SOLUTION
out = []
ia = 0 # index into list a
ib = 0 # index into list b
while ia < len(a) and ib < len(b):
# Check current items in both lists:
# - if a < b, add a and increase ia
# - else add b and increase ib
if a[ia] < b[ib]:
out.append(a[ia])
ia += 1
else:
out.append(b[ib])
ib += 1
# One list could have things remaining; add any remaining items
out.extend(a[ia:])
out.extend(b[ib:])
return out