insert.py

def insert_sort(l, inc=1):
    """Insert sort."""

    for i, x in enumerate(l):
        while x < l[i - inc] and i > 0:
            l[i] = l[i - inc]
            i -= inc
        l[i] = x


def gby_gaps(n):
    """Gonnet & Baeza-Yates gaps."""

    inc = n / 2

    while True:
        yield inc

        inc = 1 if inc == 2 else int(5.0 * inc / 11)
        if not inc:
            break


def shell_sort(l, steps=gby_gaps):
    """Shell sort."""

    for inc in steps(len(l)):
        insert_sort(l, inc)