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

Definition The cost model — three operations we count

Before any counting, we pin down exactly what we tally. Picture each array element as a physical card in a slot.

A comparison asks one yes/no question, "is card $a$ bigger than card $b$ ?" ( $a > b$ ). It reads two cards but changes nothing.
A move (shift) picks up one card and drops it into an adjacent empty slot. It is one write. Insertion sort opens a gap and slides cards one-by-one — each slide is one move.
A swap exchanges two cards' positions at once. It is two writes (each card is rewritten). Selection and bubble sort swap; insertion sort does not swap, it shifts.

So " $k$ moves" and " $k$ swaps" are not the same write-cost: a swap $= 2$ writes, a move $= 1$ write. When a problem says "moves" it means single-card shifts; "swaps" means paired exchanges. Keep these three columns separate in every count below.

Level 1 — Recognition

Goal: identify which algorithm is running just from what its work looks like.

Recall Solution L1.1

Answer: Bubble sort. Two clues, each decisive:

It swapped only adjacent pairs (5↔3, then 8↔1). Selection swaps a possibly-distant minimum into the front; insertion shifts a run of elements. Only bubble is defined by neighbour-only swaps.
The largest element 8 "floated" to the end in one pass — the signature of bubble sort, where each pass locks the current maximum at the back. (Selection would have put the minimum 1 at the front; insertion would have grown a sorted prefix on the left, giving [3,5,8,1].)

Recall Solution L1.2

Answer: Selection sort. It is the only one of the three whose comparison count is fixed regardless of input, because its inner scan to find the minimum never stops early: $\frac{n ( n - 1 )}{2} = \frac{5 \cdot 4}{2} = 10.$ Flagged bubble and insertion both adapt — on a sorted array they'd make only $n - 1 = 4$ comparisons (bubble does one clean swap-free sweep, then stops). A constant count that ignores order ⇒ selection sort.

Level 2 — Application

Goal: run each algorithm by hand, counting comparisons and moves.

Use the cost model above: count comparisons (read-questions) and moves/swaps (writes) in separate columns. The step figure below shows exactly how insertion sort opens a gap and slides cards — refer to it while tracing L2.1.

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

Recall Solution L2.1

Sorted prefix starts as [4]. (Follow the gap-and-slide panels in the figure: each grey arrow is one move.)

Insert 2: compare 2<4 (1 comp) → shift 4 right (1 move) → [2,4,5,1].
Insert 5: compare 5<4? No (1 comp) → stop, no shift → [2,4,5,1].
Insert 1: compare 1<5 yes → shift (comp 1, move 1); 1<4 yes → shift (comp 2, move 2); 1<2 yes → shift (comp 3, move 3); front reached → insert → [1,2,4,5]. Totals: comparisons $= 1 + 1 + 3 = 5$ ; moves $= 1 + 0 + 3 = 4$ . Check via inversions of [4,2,5,1]: pairs out of order are $(4, 2), (4, 1), (2, 1), (5, 1) = 4$ inversions $= 4$ moves. ✓

Recall Solution L2.2

Pass 1: compare 2>1? yes → swap → [1,2,3] (comp 1, swap 1). Compare 2>3? no (comp 2). A swap happened this pass, so the flag says "keep going."
Pass 2: compare 1>2? no (comp 3). Compare 2>3? no (comp 4). No swaps this pass → flag lets us stop. Totals: passes $= 2$ , comparisons $= 4$ , swaps $= 1$ (one swap $= 2$ writes). The second pass exists only to confirm the array is sorted — that's the price of the flag: one extra clean pass.

Recall Solution L2.3

Pass $i = 0$ : scan [3,4,1,2], min is 1 (index 2) → swap indices 0,2 → [1,4,3,2]. (3 comparisons)
Pass $i = 1$ : scan [4,3,2], min is 2 (index 3) → swap → [1,2,3,4]. (2 comparisons)
Pass $i = 2$ : scan [3,4], min is 3, already in place → no swap. (1 comparison) Totals: comparisons $= 3 + 2 + 1 = 6 = \frac{4 \cdot 3}{2}$ ✓, swaps $= 2$ (at most $n - 1 = 3$ ).

Level 3 — Analysis

Goal: reason about costs across whole classes of inputs, not one array.

The figure below plots how the comparison count grows with input size $n$ for all three sorts. Read it as three stories: the magenta curve is the shared worst case $\frac{n ( n - 1 )}{2}$ (selection always sits here; bubble and insertion sit here only on reverse-sorted input); the orange line is the best case $n - 1$ that flagged-bubble and insertion reach on already-sorted input; the violet double-arrow at $n = 20$ measures "the winning gap" — how much work the adaptive sorts save when data is tidy. Everything in L3.1–L3.2 is just reading numbers off this picture.

Recall Solution L3.1

All three worst cases are the same sum — that is why they share one magenta curve in the figure: $\frac{n ( n - 1 )}{2} = \frac{6 \cdot 5}{2} = 15.$ (a) Selection always makes $15$ (best $=$ worst — the fixed staircase). (b) Insertion makes $15$ only in the worst case: a strictly reverse-sorted array [6,5,4,3,2,1], where element $i$ must shift past all $i$ predecessors. This array has the maximum $(2 6) = 15$ inversions — every pair is out of order. (c) Flagged bubble also makes $15$ on reverse-sorted input: pass $k$ compares $n - k$ neighbours, and $\sum_{k = 1}^{n - 1} (n - k) = \frac{n ( n - 1 )}{2} = 15$ . On reverse-sorted data every sweep swaps something, so the flag never triggers early. The three counts agree — they differ only in best and average behaviour, not worst.

Recall Solution L3.2

Selection: $\frac{100 \cdot 99}{2} = 4950$ comparisons. Insertion best case (already sorted): $n - 1 = 99$ comparisons. $ratio = \frac{4950}{99} = 50.$ So on already-sorted data of size 100, selection does 50× the comparison work of insertion. This gap widens with $n$ — it is $\frac{n ( n - 1 ) /2}{n - 1} = \frac{n}{2}$ , i.e. grows without bound. That single fact is why insertion sort wins on ordered data (it is the violet double-arrow in the figure, growing as $n$ grows).

Recall Solution L3.3

Inversion count. List pairs $i < j$ with $A [i] > A [j]$ : $(5, 2), (5, 3), (6, 3)$ → $3$ inversions. So insertion sort will do exactly 3 moves (single-card shifts). Trace check:

Insert 5: 5>1 stop, 0 moves.
Insert 2: 2<5 shift (1), 2>1 stop → 1 move.
Insert 6: 6>5 stop, 0 moves.
Insert 3: 3<6 shift (1), 3<5 shift (1), 3>2 stop → 2 moves. Total moves $= 1 + 2 = 3$ ✓ — matches the inversion count exactly.

Level 4 — Synthesis

Goal: combine ideas — choose or design an algorithm for a stated constraint.

Recall Solution L4.1

Choose selection sort. It performs at most $n - 1$ swaps — one per pass — because each pass places exactly one element permanently. Every other element is read many times but written rarely. For $n = 1000$ : at most $n - 1 = 999$ swaps. Using the cost model (a swap $= 2$ writes), that is at most $1998$ writes. Contrast: insertion/bubble can perform up to $\frac{n ( n - 1 )}{2} = 499500$ moves on bad input — catastrophic for write-limited storage. Here the comparison count of selection ( $499500$ ) is irrelevant because reads are cheap.

Recall Solution L4.2

Insertion is cheaper when $\frac{1}{4} n^{2} < 2 n lo g_{2} n .$ The key step — why we divide by $n$ : both sides contain a factor of $n$ , and for any array size $n \geq 1$ that factor is strictly positive. Dividing an inequality by a positive quantity keeps the direction of " $<$ " unchanged (only dividing by a negative would flip it). So we may cancel one $n$ from each side safely: $\frac{1}{4} n < 2 lo g_{2} n .$ This is worth doing because it turns a quadratic-vs- $n lo g n$ comparison into a linear-vs-log one, which is far easier to test by hand. Now test integers:

$n = 16$ : $8 lo g_{2} 16 = 8 \cdot 4 = 32 > 16$ ✓ (insertion cheaper).
$n = 32$ : $8 lo g_{2} 32 = 8 \cdot 5 = 40 > 32$ ✓.
$n = 43$ : $8 lo g_{2} 43 \approx 8 \cdot 5.426 = 43.4 > 43$ ✓.
$n = 44$ : $8 lo g_{2} 44 \approx 8 \cdot 5.459 = 43.7 < 44$ ✗ (fast sort cheaper). (Here $\frac{1}{4} n < 2 lo g_{2} n$ is multiplied through by 4 to give $n < 8 lo g_{2} n$ for the arithmetic.) Crossover: insertion wins for $n \leq 43$ . This is exactly why real libraries like Timsort and Introsort set an insertion-sort cutoff in the tens of elements.

Level 5 — Mastery

Goal: prove a general statement and confront the deepest subtleties.

Recall Solution L5.1

(a) Insertion is stable. When inserting A[i], the inner loop shifts a predecessor right only while it is strictly greater than A[i] (the comparison is >), and stops as soon as it meets an element ≤ A[i]. So an earlier equal key is never shifted past A[i]; A[i] lands after all equal keys already placed. Original order among equals is preserved. ∎ (b) Selection is not stable. Take [2a, 2b, 1] (two keys equal to 2, subscripts mark original order).

Pass 0: scan finds min 1 at index 2, swaps it with index 0 → [1, 2b, 2a].
Pass 1: [2b, 2a] already in min-first order, no swap. Result: [1, 2b, 2a] — the two 2's are now b before a, the reverse of their input order. Stability broken by a single long-distance swap. ∎

Recall Solution L5.2

Where the $n lo g_{2} n$ floor comes from (so we don't invoke it blindly). A comparison sort must be able to distinguish all $n!$ possible input orderings. Each comparison has 2 outcomes (yes/no), so $c$ comparisons distinguish at most $2^{c}$ orderings. To separate all $n!$ we need $2^{c} \geq n!$ , i.e. $c \geq lo g_{2} (n!) .$ By Stirling's approximation $lo g_{2} (n!) = n lo g_{2} n - n lo g_{2} e + O (lo g n) = n lo g_{2} n (1 - o (1))$ , so the information-theoretic floor is $c ≳ n lo g_{2} n$ up to a lower-order $- n lo g_{2} e \approx - 1.44 n$ term and constants. This is a floor (a minimum), not a ceiling. For $n = 1024 = 2^{10}$ , using the leading term $n lo g_{2} n$ as the benchmark:

Selection: $\frac{1024 \cdot 1023}{2} = 523776$ comparisons.
Leading-term floor: $n lo g_{2} n = 1024 \cdot 10 = 10240$ comparisons. Ratio $= \frac{523776}{10240} \approx 51.2$ . Selection does roughly 51× the necessary comparison work at this size. The "waste" is the price of never reusing information across passes — each scan rediscovers order from scratch. Merge sort avoids this by remembering sorted sub-results.

Recall Solution L5.3

There are exactly $(2 n) = \frac{n ( n - 1 )}{2}$ unordered pairs of positions. Each pair is either in order or inverted — never both. So the inversion count can be at most the total number of pairs, $\frac{n ( n - 1 )}{2}$ . This maximum is attained iff every pair is inverted, i.e. the array is strictly decreasing: [n, n-1, …, 2, 1]. Implication: for the standard one-by-one shifting implementation of insertion sort (the only version we use here, where each element moves one slot at a time), the number of moves equals the inversion count exactly — because each single shift removes precisely one inversion. So its absolute worst case is a reverse-sorted array, costing exactly $\frac{n ( n - 1 )}{2}$ moves, matching the $O (n^{2})$ bound from the parent note. (Subtlety: a variant that finds the insertion point by binary search and then does one block move of the tail still performs $\frac{n ( n - 1 )}{2}$ element writes on reverse input, but its count of discrete "move operations" is bookkept differently. The clean "moves $=$ inversions" identity is specifically about the element-at-a-time shift.) ∎

Recall One-line summary of every level

Recognize by fingerprint (L1) → trace and count (L2, using the move/swap/comparison cost model) → reason over input classes via inversions (L3) → choose/design under constraints (L4) → prove stability, lower bounds, and extremes (L5).

← Back to the topic note · Related: Inversions and Counting · Stability in Sorting · Big-O Notation · Timsort · Introsort