Insertion Sort

def insert(L: list, b: int) -> None:
    """Precondition: L[0:b] is already sorted.
    Insert L[b] where it belongs in L[0:b + 1].
    
    >>> L = [3, 4, -1, 7, 2, 5]
    >>> insert(L, 2)     # L[0] & L[1] are sorted
    >>> L
    [-1, 3, 4, 7, 2, 5]
    >>> insert(L, 4)     # L[0:4] are sorted
    >>> L
    [-1, 2, 3, 4, 7, 5]
    """
    
    # Find where to insert L[b] by searching backwards from L[b]
    # for a smaller item.
    i = b
    while i != 0 and L[i - 1] >= L[b]:
        i = i - 1
        
    # Move L[b] to index i, shifting the following values to the right.
    value = L[b]
    del L[b]
    L.insert(i, value)
    
def insertion_sort(L: list) -> None:
    """Reorder the items in L from smallest to largest.
    >>> L = [3, 4, 7, -1, 2, 5]
    >>> insertion_sort(L)
    >>> L
    [-1, 2, 3, 4, 5, 7]
    """
    
    i = 0
    while i != len(L):
        insert(L, i)
        i = i + 1

if __name__ == '__main__':
    L = [3, 4, -1, 7, 2, 5]
    insertion_sort(L)
    print(L)

# Run the following to see whether the design is okay:
#    import doctest
#    doctest.testmod()