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 / 315
3
8
1
9
2
7
4
8 numbers, out of order. Press play — or step through one comparison at a time.
📖 In depth — the full reference
The sorting scoreboard (for reference across all five sorting lessons)
| algorithm | best | average | worst | extra space | stable? |
|---|---|---|---|---|---|
| bubble | O(n) with early exit | O(n²) | O(n²) | O(1) | yes |
| selection | O(n²) — always | O(n²) | O(n²) | O(1) | no (long-range swaps) |
| insertion | O(n) on sorted input | O(n²) | O(n²) | O(1) | yes |
| merge | O(n log n) | O(n log n) | O(n log n) | O(n) | yes |
| quick | O(n log n) | O(n log n) | O(n²) (bad pivots) | O(log n) stack | no (typical) |
| Timsort (stdlib) | O(n) | O(n log n) | O(n log n) | O(n) | yes |
Insertion sort — everything worth knowing
- Invariant: after step i, the first i+1 elements are sorted AMONG THEMSELVES (not final positions yet — that is the difference from selection sort).
- ADAPTIVE — its defining virtue: runtime is O(n + d) where d = number of inversions (out-of-order pairs). Nearly-sorted data: nearly O(n). This is why it appears inside production sorts.
- Stable: the shifting scan stops at the first equal-or-smaller element, never jumping over equals.
- Online: it can sort a stream as items ARRIVE, holding a sorted hand at all times — like the card player.
- Real systems use it for small slices: Timsort switches to insertion sort under ~32 elements, because for tiny n the simple loop beats clever recursion's overhead.
Python corner: bisect — insertion sort's fast half
import bisect hand = [3, 7, 11, 18] spot = bisect.bisect_left(hand, 9) # O(log n) — WHERE to insert bisect.insort(hand, 9) # O(n) — the shift still costs print(hand) # [3, 7, 9, 11, 18] # Finding the spot: binary search (next lessons!). Making room: O(n). # That O(n) shift is why a sorted list is not a database index.
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…
Practice — write it yourself
insertion_sort(arr): grow a sorted left side; take each next card and shift bigger cards right until it fits. The way humans sort a hand of cards. (No sorted() allowed!)
Python 3 · runs in your browser · your draft is saved locally
📝 My notessaved in this browser