def insort_first(list, key):
    """
    Insert the given key at its earliest position in sorted order.
    Return the resulting list.
    """
    if list == ():
        return (key, ())
    else:
        head, tail = list
        if key <= head:
            return (key, list)
        else:
            return (head, insort_first(tail, key))