ZERO / HERO
Sorting a hand of cards

Insertion Sort

The analogy

You pick up cards one at a time and slide each into the right spot among the cards already in your hand. The left side of your hand is always sorted and grows by one each turn. If the cards arrive nearly sorted, you barely move anything.

Visualizer

Watch the hand fill

step 1 / 31
5
3
8
1
9
2
7
4

8 numbers, out of order. Press play — or step through one comparison at a time.

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]      # slide right
            j -= 1
        a[j + 1] = key
    return a
# nearly-sorted input -> nearly O(n)
Check yourself

Insertion sort is fastest when the input is…