Visual walkthrough — Bubble sort, selection sort, insertion sort — O(n²), when insertion sort wins

We will build one idea at a time:

1. What "sorted" and "out of order" even look like.
2. What insertion sort physically does to a card.
3. Why one slide = removing exactly one out-of-order pair.
4. Why that makes the total work a count of out-of-order pairs.
5. The best case, the worst case, and the average — all as pictures.

Nothing below assumes you remember any formula. If a symbol appears, it was drawn first.

Step 1 — What does "out of order" look like?

WHAT. Line up the numbers of an array as bars, left to right. If the array is sorted, the bars only ever go up as you walk rightward — like a staircase climbing. Any place where a taller bar sits to the left of a shorter bar is a spot that is "wrong".

WHY. Before we can count work, we need a precise, visible name for "wrongness". That name is the inversion.

PICTURE. Below, the pink connecting lines join every left-taller pair. A sorted array would have zero pink lines.

Step 2 — What one move of insertion sort looks like

WHAT. Insertion sort keeps a sorted prefix on the left (already tidy) and an untouched suffix on the right. It picks the first untouched card, call its value $x$, and slides it leftward, one neighbour at a time, until the card to its left is $\le x$.

WHY. This is exactly how you sort a hand of playing cards: you never re-shuffle the whole hand, you just tuck each new card into the part you already hold. It is the cheapest possible way to grow an ordered list by one element.

PICTURE. The blue box is the sorted prefix; the yellow card is $x$ leaving the suffix; the arrow shows it sliding into the blue box.

Step 3 — One slide removes exactly one inversion

WHAT. Watch a single shift: a bigger neighbour on the left steps right by one slot, and our card $x$ steps left by one slot. Those two bars have just swapped their left/right order.

WHY. This is the heart of the whole page. Before the swap, that specific pair was left-taller — a pink line, an inversion. After the swap it is left-shorter — the pink line is gone. And no other pair changed its order, because only these two adjacent bars moved relative to each other.

PICTURE. The "before" has a pink crossing between the two boxed bars; the "after" has none. One shift, one pink line erased.

Step 4 — Total moves = total inversions

WHAT. Since every shift erases exactly one inversion, and the algorithm stops only when zero inversions remain, the total number of shifts must equal the number of inversions the array started with.

WHY. Think of the inversions as a jar of marbles. Each shift removes one marble. You are done when the jar is empty. So the number of shifts = the number of marbles you began with — no more, no less.

PICTURE. A running tally: each pass drains some marbles from the jar; the bar chart of "marbles removed per pass" sums to the starting inversion count.

Step 5 — The best case: already sorted → $O(n)$

WHAT. If the array is already sorted, there are zero pink lines. Every card we pick up finds its left neighbour is $\le$ it immediately, so the stopping rule fires after one comparison and zero shifts.

WHY. We still have to look at each card once to confirm it belongs where it is — that is the "$n$" of $O(n)$. But we never move anything, because there are no marbles in the jar.

PICTURE. A clean rising staircase; each card gets a single green tick ("already in place") and no arrow at all.

This is the number that beats selection sort — which the parent shows is stuck at $\frac{n(n-1)}{2}$ comparisons no matter what.

Step 6 — The worst case: reverse-sorted → $O(n^2)$

WHAT. Now flip the array to a descending staircase. Here every pair is a pink line: the card at position $i$ is smaller than all $i$ cards to its left, so it must shift past every one of them.

WHY. This is the fullest possible jar of marbles. Card 1 shifts past 1, card 2 past 2, … card $n-1$ past $n-1$. Adding these up counts every pink line in a fully-crossed picture.

PICTURE. A descending staircase with every pair joined by a pink line — a full triangular mesh. Counting the mesh lines gives $\frac{n(n-1)}{2}$.

Step 7 — The average case, and the degenerate inputs

WHAT. A random array sits between the two extremes. On average about half of all pairs are inversions, so $\text{inv}(A)\approx \frac{1}{2}\cdot \frac{n(n-1)}{2}=\frac{n(n-1)}{4}$ — still $O(n^2)$, but with half the constant of the worst case.

WHY. For any two distinct values, they are equally likely to be in order or out of order in a random shuffle. So on average a random arrangement carries half the maximum number of pink lines.

Degenerate inputs — nothing breaks:

• Empty array ($n=0$) ::: no cards, no comparisons, done. $\text{inv}=0$.
• One element ($n=1$) ::: the prefix is already the whole array; the loop never runs. $\text{inv}=0$.
• All equal values ::: no pair is strictly left-bigger, so $\text{inv}=0$ → linear, and equal cards keep their order (stable).

PICTURE. A number line of "disorder" from 0 to $\frac{n(n-1)}{2}$, with the three inputs (sorted, random, reversed) marked, and the cost curve tracking it.

The one-picture summary

Everything above compressed: insertion sort is a machine that drains inversions, one adjacent shift at a time. Total moves = starting pink lines. Fewer pink lines (tidy input) → linear and it wins. Full mesh (reversed) → quadratic.

#flashcards/coding