Insertion sort.

gistfile1.py

from operator import lt


def insertion_sort(data, cmp_func=lt):
    for i in xrange(1, len(data)):
        if cmp_func(data[i], data[i - 1]):
            el = data.pop(i)
            j = i - 1
            while j > 0 and cmp_func(el, data[j - 1]):
                j -= 1
            data.insert(j, el)
    return data


def test():
    for i in xrange(1, 10):
        data = list(reversed(range(i)))
        assert insertion_sort(data) == sorted(data)


if __name__ == '__main__':
    test()