Iterates through the list, starting at the second item and then iterating backwards and inserting before the last valid (i.e. larger if ascending) number.

Implementation

from random import randint
data = [randint(1, 100) for x in range(10)]

def insertion_sort(arr: list[int]) -> None:
	for i in range(1, len(arr)):
		current = arr[i]
		v = i - 1
		while v >= 0 and current < arr[v]:
			v -= 1
		arr.insert(v + 1, arr.pop(i))

insertion_sort(data)
print(data)

Advantages

• Faster than Bubble Sort
• Easy to program
• Fast on small datasets
• O(1) space

Disadvantages

• Slow on large datasets