Skip to content

Instantly share code, notes, and snippets.

@alcides

alcides/lazy_insertion_sort.py

Created July 20, 2021 08:19
Show Gist options
  • Save alcides/20595c4b9fc8aeab7a9918f1bd334ae1 to your computer and use it in GitHub Desktop.
Save alcides/20595c4b9fc8aeab7a9918f1bd334ae1 to your computer and use it in GitHub Desktop.
Download ZIP
Insertion sort written in generators (to simulate haskell), so the head of a sorted list has linear complexity.
Raw
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment