def merge(left, right):
    """
    Merges two sorted lists.
    left  = A sorted list.
    right = A sorted list.
    Examples
        merge([2,4],[1,3])
        # => [1,2,3,4]
    Complexity: O(n1 + n2)
    Returns the sorted list post merge.
    """

    merged = []

    # while at least one list has elements
    while left or right:

        if left and right:
            if left[0] <= right[0]:
                key = left.pop(0)
            else:
                key = right.pop(0)
        elif left:
            key = left.pop(0)
        else:
            key = right.pop(0)

        merged.append(key)

    return merged