def merge(A,B):
    # assume A, B sorted
    # return X := combination of A and B, sorted
    i = 0                       # index into A
    j = 0                       # index into B
    X = []
    while i < len(A) or j < len(B):
        # find the minimum between A[i] (if it exists) and
        # B[j] (if it exists)
        # Two cases:
        #   1) we append A[i], then i = i + 1
        #   2) we append B[j], then j = j + 1
        if i < len(A) and (j >= len(B) or A[i] <= B[j]):
            X.append(A[i])
            i = i + 1
        else:
            X.append(B[j])
            j = j + 1
    return X