Insertion Sort
Easy+50 XPGrow a sorted prefix by inserting each next element into its correct spot.
No visualization loaded.
Watch
—
Press Run to begin.
Insertion sort is how most people sort playing cards in their hand. Keep a sorted group on the left. Pick up the next card and slide it left until it sits in the right spot among the cards you've already sorted. The sorted group grows by one each time, until the whole hand is in order.
▸What's a 'sorted prefix'?
It's the chunk on the left that's already in order. At the start it's just the first card (one card is trivially sorted). Each round you take the next card and insert it into this chunk, so the sorted prefix grows by one — until it covers the whole array.
▸How is this different from bubble sort?
Bubble sort makes repeated full passes swapping any out-of-order neighbours. Insertion sort handles one new card at a time, only shifting within the already-sorted part. In practice insertion sort does less work on nearly-sorted data — if a card is already in the right place, it stops immediately.
▸So what's its speed?
Worst case it's still O(n²) (every new card has to slide past all the others), so it's not for huge random arrays. But its best case is O(n): on already-sorted or nearly-sorted data each card barely moves. That 'fast when almost sorted' property makes it genuinely useful, and it's why real libraries use it for small chunks.
▸Why learn two O(n²) sorts?
Because they teach two different mental moves — 'repeatedly swap' (bubble) vs 'insert into a sorted part' (insertion). The 'grow a sorted region' idea here is the seed of merge sort next, where we sort two halves and combine them. Each sort builds intuition for the faster one after it.
How the work grows
O(n²) worst, O(n) nearly sorted is slow — explodes on big inputs. Worst case every new card slides past all the others (n×n), so the curve climbs like bubble sort. But on already-near-sorted data each card barely moves, dropping toward the straight O(n) line. Sorts in place.
Faint dotted lines = O(1) (flat) and O(n) (straight) for comparison.