Insertion Sort

INSERTION SORT(A)

for j = 2 to A.length
    key = A[j]
    i = j - 1
    while i > 0 and A[i] > key
        A[i+1] = A[i]
        i = i - 1
    A[i+1] = key



In [90]:

    
import random


def insertion_sort(numbers):
    for j in range(1, len(numbers)):
        key = numbers[j]
        i = j - 1
        while i >= 0 and numbers[i] > key:
            numbers[i+1] = numbers[i]
            i -= 1
        numbers[i+1] = key
    return numbers
        

# generate a list of 10 random numbers
numbers = [random.randrange(1, 100) for i in range(10)]

# verify that the algorithm is correct
assert insertion_sort(numbers) == sorted(numbers)