insertion_sort.py

def insertion_sort(lst):
    """
    >>> insertion_sort([3, 4, 2, 10, 1])
    [1, 2, 3, 4, 10]
    >>> insertion_sort([1, 2, 3, 4, 5])
    [1, 2, 3, 4, 5]
    >>> insertion_sort([])
    []
    """
    for i in xrange(1, len(lst)):
        tmp = lst[i]
        j = i
        while j > 0 and lst[j - 1] > tmp:
            lst[j] = lst[j - 1]
            j -= 1
        lst[j] = tmp
    return lst

if __name__ == '__main__':
    import doctest
    doctest.testmod(verbose=False)