Insertion Sort
Sort cards as you pick them up: take each new value and slide it left until it's in the right place.
Slide each card into place
- comparisons
- 0
- result
- —
- 0
def insertion_sort(arr): - 1
for i in range(1, len(arr)): - 2
key = arr[i] - 3
j = i - 1 - 4
while j >= 0 and arr[j] > key: - 5
arr[j + 1] = arr[j] - 6
j -= 1 - 7
arr[j + 1] = key
What you just watched
Insertion sort treats the front of the array as "already sorted" and pulls one new value off the unsorted side at a time. Each value walks left, comparing with its neighbour and swapping when it's smaller, until it lands. Worst case O(n²); best case O(n) when the array is already nearly sorted (each new value travels almost no distance).
Try the Worst case button (a fully reversed array) — every new value has to slide all the way to the front. Then click Sort on a freshly-shuffled array and watch how often a value lands almost immediately.
Insertion sort is what most people accidentally invent when asked to sort cards in their hand. It's also the algorithm hybrid sorts (like Timsort) fall back to for small subarrays — the constant factors are tiny, so for n ≲ 16 it beats fancier sorts.