Merge two sorted lists

Keep one index into each list and always take the smaller of the two front items.

def merge(a, b):
    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.extend(a[i:])
    out.extend(b[j:])
    return out

Each comparison places one item, and when one list runs out the rest of the other is already sorted. This is the "merge" step of merge sort. Using <= keeps equal items in their original order, which makes the sort stable.