Insertion sort written in generators (to simulate haskell), so the head of a sorted list has linear complexity.

lazy_insertion_sort.py

def insert_sort_generator(li):
    if len(li) <= 0:
        return
    h = li[0]
    done = False
    for v in insert_sort_generator(li[1:]):
        if h < v and not done:
            yield h
            done = True
        yield v
    if not done:
        yield h


print(list(insert_sort_generator([3,2,1,4,5,6])))
    
x = next(insert_sort_generator([3,2,1,4,5,6]))
print(x)