def merge(left: list[int], right: list[int]) -> list[int]:
    """Merge two sorted lists into a sorted list."""
    out = []
    # move through both lists, doing comparisons
    while len(left) and len(right):
        if left[0] < right[0]:
            out += [left.pop(0)]
        else:
            out += [right.pop(0)]

    # append any elements left
    out += left + right
    return out