Bubble sort, selection sort, insertion sort — O(n²), when insertion sort wins: Worked examples

Two words we count throughout, defined in plain terms so no symbol is unearned:

We also reuse the parent's key idea:

The scenario matrix

Every sorting input falls into one of these case classes. Each row is a distinct shape of data that makes the three sorts behave differently.

#	Case class	What the input looks like	Which sort this stresses
A	Already sorted (best case)	`[1,2,3,4,5]`	separates adaptive (insertion/bubble) from blind (selection)
B	Reverse sorted (worst case)	`[5,4,3,2,1]`	maximum inversions — worst for all three
C	All elements equal (degenerate)	`[7,7,7,7]`	tests early-stop and stability
D	One element out of place (nearly sorted)	`[1,2,3,4,0]`	the real-world "why insertion wins" case
E	Random / general mix	`[4,2,5,1,3]`	the average case
F	Single element / empty (limiting)	`[9]`, `[]`	boundary: what does $n = 1, 0$ give?
G	Stability twist (equal keys with tags)	`[(2,a),(1,b),(2,c)]`	shows selection breaking, insertion keeping order
H	Word problem (real data)	daily temperatures, one late reading	picks the right sort for the job

The 8 examples below hit every cell A–H.

Example A — Already sorted (best case)

Worked example Sort

[1, 2, 3, 4, 5] with insertion vs selection. Cell A. Forecast: Which does fewer comparisons — and by how much?

Insertion sort:

Prefix [1]. Take 2: compare with 1 → 2 > 1, stop. Why this step? Once the new element is $\geq$ its left neighbour, everything left is already smaller, so no shift is needed.
Take 3: compare with 2 → stop. Take 4: compare with 3 → stop. Take 5: compare with 4 → stop.
Each of the $4$ new elements did exactly 1 comparison, 0 moves. Why? The array was already ordered → zero inversions.

Total: $4$ comparisons, $0$ moves $= n - 1 = O (n)$ .

Selection sort:

Pass finds min of all 5 → it's 1, already at front. Compares $4$ times. Why so many? Selection never trusts the order; it scans the whole unsorted part every pass.
Next passes: $3 + 2 + 1$ more comparisons.

Total: $4 + 3 + 2 + 1 = 10$ comparisons $= \frac{5 \cdot 4}{2}$ .

Verify: insertion $= n - 1 = 4$ ✓; selection $= \frac{n ( n - 1 )}{2} = 10$ ✓. Insertion is $2.5 \times$ cheaper here — the whole point of the parent note.

Example B — Reverse sorted (worst case)

Example C — All elements equal (degenerate)

Example D — One element out of place (the "insertion wins" case)

Worked example Sort

[1, 2, 3, 4, 0] — sorted except the 0 sneaked to the end. Cell D. Forecast: Insertion does $O (n)$ or $O (n^{2})$ here?

Insertion sort:

Take 2: 2>1 stop (1 comp). Take 3: stop (1). Take 4: stop (1). Why? The whole prefix [1,2,3,4] is already sorted, so each new element parks after one check.
Take 0: 0<4 shift, 0<3 shift, 0<2 shift, 0<1 shift → insert at front. 4 comparisons, 4 moves.

Totals: comparisons $1 + 1 + 1 + 4 = 7$ ; moves $= 4$ .

Selection sort on the same input: fixed $\frac{5 \cdot 4}{2} = 10$ comparisons — it can't tell only one element is wrong.

Verify: inversions of [1,2,3,4,0]: the 0 sits after 1,2,3,4, each a pair out of order $= 4$ inversions $=$ 4 moves ✓. Insertion's $7$ comparisons $<$ selection's $10$ ✓. This is $O (n + inv) = O (n)$ behaviour — the headline result made concrete. See Inversions and Counting.

Example E — Random mix (average case), with a figure

Worked example Bubble sort on

[4, 2, 5, 1, 3], pass by pass. Cell E. Forecast: Which element locks in place first, and where?

The figure below traces every pass. Follow the amber box (the element being compared) and the cyan brace (the already-locked sorted tail).

Pass 1 over [4,2,5,1,3]: compare 4,2→swap; 4,5→ok; 5,1→swap; 5,3→swap. Result [2,4,1,3,5]. Why did 5 end up last? Bubble carries the running maximum rightward until it "floats" to the end — after pass 1 the largest is locked.
Pass 2 over first 4: 2,4ok; 4,1swap; 4,3swap → [2,1,3,4,5]. 4 locked.
Pass 3 over first 3: 2,1swap; 2,3ok → [1,2,3,4,5]. 3 locked.
Pass 4 over first 2: 1,2ok, no swap → flag says "done", stop early.

Comparisons: $4 + 3 + 2 + 1 = 10$ (but pass 4's flag lets us skip the would-be pass 5). Swaps: count them — $1$ (p1: 4/2) $+ 1$ (5/1) $+ 1$ (5/3) $+ 1$ (p2: 4/1) $+ 1$ (4/3) $+ 1$ (p3: 2/1) $= 6$ .

Verify: the input [4,2,5,1,3] has $6$ inversions (pairs: (4,2),(4,1),(4,3),(2,1),(5,1),(5,3)) $= 6$ swaps ✓ — bubble's adjacent swaps also equal the inversion count.

Example F — Single element and empty array (limiting inputs)

Example G — Stability twist (equal keys with tags)

Worked example Sort by number only:

[(2,a), (1,b), (2,c)]. Does a stay before c? Cell G. Forecast: Which sort keeps the original a-before-c order for the two 2s?

A sort is stable if elements with equal keys keep their input order. Here (2,a) came before (2,c); a stable sort must preserve that.

Insertion sort (shifts, stops at equal):

Prefix [(2,a)]. Take (1,b): 1<2 shift, insert → [(1,b),(2,a)].
Take (2,c): compare key 2 with (2,a)'s key 2 → is 2 < 2? No, stop. Insert after (2,a) → [(1,b),(2,a),(2,c)]. Why after? The strict-less test means we never jump past an equal key, so a stays ahead of c. Stable ✓.

Selection sort (long-distance swap):

Scan for min key: 1 at index 1. Swap index 0 and 1 → [(1,b),(2,a),(2,c)]. Here the swap happened to be harmless. But consider [(2,a),(2,c),(1,b)]: min 1 is at index 2, swap it to front → [(1,b),(2,c),(2,a)]. Now c jumped ahead of a! Why? Selection's swap flings a distant element over equals it never compared. Not stable ✗.

Verify: insertion output [(1,b),(2,a),(2,c)] preserves a<c ✓; selection on [(2,a),(2,c),(1,b)] yields [(1,b),(2,c),(2,a)] which flips them ✓ (order broken). Matches Stability in Sorting and the parent's mistake callout.

Example H — Word problem (real data, pick the sort)

Worked example A weather station logs daily highs, already in date order and thus sorted by value most of the year. One sensor glitch inserts yesterday's reading late, giving

[12, 14, 15, 17, 19, 16]. You must re-sort. Cell H. Forecast: Which of the three sorts finishes fastest, and why is this the textbook "insertion wins" situation?

The array is sorted except the trailing 16, which belongs between 15 and 17. Why does this shape matter? Real logs, time-series, and "append then fix" data are almost always nearly sorted — the parent note's exact winning condition.
Insertion: 14,15,17,19 each stop after 1 compare (4 comparisons, 0 moves). Take 16: 16<19 shift, 16<17 shift, 16>15 stop, insert → [12,14,15,16,17,19]. That's 2 comparisons + a final stop-compare = 3 comparisons, 2 moves for the 16.
Total insertion comparisons $= 1 + 1 + 1 + 1 + 3 = 7$ ; moves $= 2$ (only two elements shifted right).
Selection would do a blind $\frac{6 \cdot 5}{2} = 15$ comparisons no matter what.

Verify: inversions in [12,14,15,17,19,16]: only (17,16) and (19,16) are out of order $= 2$ inversions $= 2$ moves ✓. Insertion's $7$ comparisons vastly beat selection's $15$ ✓. Verdict: use insertion sort. Units check: "comparisons" and "moves" are pure counts (dimensionless), consistent throughout. For huge datasets you'd escalate to Timsort — which itself falls back to insertion sort on small nearly-sorted runs.

Recall Quick self-test across all cells

Best case for insertion, and its cost ::: already sorted (Cell A/D) → $n - 1$ comparisons, $O (n)$ . Worst case, and its move count ::: reverse sorted (Cell B) → $\frac{n ( n - 1 )}{2}$ moves = all inversions. What does every sort do on an all-equal array ::: insertion/bubble stop early → $n - 1$ comparisons, 0 moves; selection still $\frac{n ( n - 1 )}{2}$ . Comparisons on [] or [9] ::: $0$ — the loop bound $n - 1 \leq 0$ runs nothing. Why selection can break stability ::: a long-distance swap can fling an element past an equal key it never compared. The real-world case where insertion clearly wins ::: nearly-sorted data (Cell H) → cost $O (n + inversions) \approx O (n)$ .

See also: Big-O Notation · Inversions and Counting · Stability in Sorting · Merge Sort · Quicksort · Introsort · Lower Bound for Comparison Sorts.

#flashcards/coding

Insertion sort comparisons on [1,2,3,4,5]

n - 1 = 4

(best case,

O (n)

Insertion sort comparisons and moves on [4,3,2,1]

6

comparisons,

6

moves (worst case,

= \frac{n ( n - 1 )}{2}

Moves made by insertion sort on an all-equal array

0

— the strict-less test triggers an immediate stop.

Comparisons of selection sort on any 5-element array

always

10 = \frac{5 \cdot 4}{2}

, independent of order.

Why insertion sort wins on [1,2,3,4,0]

only 4 inversions → 4 moves,

O (n + inv) = O (n)

, versus selection's fixed 10 comparisons.