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

A picture to hold in your head

The whole D5 bank turns on one contrast: how the three sorts respond as the input goes from already sorted (0 inversions) to reverse sorted (the most inversions). The figure below plots the number of comparisons each performs versus how disordered the array is — watch selection stay a flat line while insertion climbs from the floor.

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

The dashed grey curve is insertion sort's average case: for a randomly-shuffled array the expected inversion count is about half of the maximum (each of the $(2 n)$ pairs is out of order with probability $\frac{1}{2}$ ), so it lands roughly halfway up — still $Θ (n^{2})$ , but with about half the moves of the reverse-sorted worst case.

True or false — justify

TF — "All three sorts are

O (n^{2})

, so on any input they take the same time."

False. Big-O is a worst-case ceiling; on already-sorted data insertion and flagged-bubble finish in

O (n)

while selection still grinds through

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

comparisons.

TF — "Selection sort's comparison count depends on how shuffled the input is."

False. Its inner scan always reads every remaining element to find the true minimum, so the count is fixed at

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

for best, average, and worst inputs alike.

TF — "Insertion sort's best, average, and worst cases are all the same Big-O."

False. Best is

O (n)

(sorted input), but average and worst are both

Θ (n^{2})

— a random array averages about

\frac{n ( n - 1 )}{4}

inversions, half the reverse-sorted maximum, so it still scales quadratically.

TF — "Insertion sort is a stable sort."

True. It only shifts elements one slot to the right and drops the new key in when it meets something less-than-or-equal, so equal keys never leap past one another.

TF — "Selection sort is stable because it moves so few elements."

False. Few writes ≠ stable. Swapping a far-away minimum into place can hop it over an equal key, reversing their order — see Stability in Sorting.

TF — "Bubble sort with a swap-flag can detect a sorted array in one pass."

True. If a full pass performs zero swaps, no adjacent pair is out of order, so the array is sorted and we stop — that's the

O (n)

best case.

TF — "Selection sort minimises the number of element writes/swaps."

True. It does at most

n - 1

swaps (one per position), which is why it's chosen when writes are physically expensive, like flash-memory wear.

TF — "A reverse-sorted array is the worst case for insertion sort."

True. Every new element must shift past all its predecessors, giving the maximum

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

inversions and full

O (n^{2})

work.

TF — "Since insertion and bubble share the same worst-case Big-O, they're interchangeable in practice."

False. Insertion does far fewer moves on average and is the fallback inside real libraries like Timsort and Introsort; bubble is essentially never used.

TF — "Insertion sort's move count equals the array's inversion count."

True. Each single-slot shift removes exactly one inversion, so total shifts = total inversions — the link explored in Inversions and Counting.

Spot the error

Error — "Selection sort can quit early once the remaining part looks sorted."

Wrong: selection's inner loop is a minimum-finding scan, not an ordering check. To be certain it has the true minimum it must inspect every remaining element, because any unseen element could be smaller than the best-so-far — there is no partial signal that lets it stop before the end.

Error — "Insertion sort is

O (n)

overall because its inner loop sometimes stops early."

The early stop only fires when the new element meets a not-greater neighbour, which happens on the first comparison only for sorted/nearly-sorted input. Reverse-sorted data never triggers it — every new element is smaller than all predecessors, so the inner loop runs fully, restoring

O (n^{2})

Error — "Bubble sort is

O (n)

in the average case."

No — a random array has

Θ (n^{2})

inversions and each bubble pass removes at most

n - 1

of them by adjacent swaps, so it needs

Θ (n)

passes on average. Only the best case (already sorted, with a swap-flag) reaches

O (n)

Error — "Adding a swap-flag makes bubble sort's worst-case swaps drop to

O (n)

The flag only lets the outer loop terminate once a swap-free pass proves sortedness; it never removes a needed swap. On reverse-sorted input every element is out of order, so it still performs

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

swaps regardless of the flag.

Error — "You can make selection sort stable by choosing the last minimum instead of the first."

The instability comes from the long-distance swap that lifts a distant minimum over the elements between it and the target slot — including equal keys. Picking a different minimum index changes which keys get hopped, not the fact that the single swap can hop equal keys, so it stays unstable.

Error — "Counting comparisons alone tells you which sort is faster."

Moves/writes matter too. Selection makes

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

comparisons but only

n - 1

writes, while insertion can do up to

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

shifts — so which one "wins" depends on whether comparisons or writes dominate the cost model.

Why questions

Why does insertion sort adapt to how disordered the input is, but selection sort does not?

Insertion's work is proportional to the number of inversions it must remove, so tidy input means little work; selection always performs its full fixed scan regardless of order.

Why do libraries fall back to insertion sort for tiny sub-arrays inside faster algorithms?

On small

n

its low constant factor and

O (n)

behaviour on near-sorted chunks beat the overhead of recursion in Merge Sort or Quicksort.

Why is the sum

1 + 2 + \dots + (n - 1)

equal to

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

, and why do both selection and insertion produce it?

Write the sum forwards and backwards and add termwise:

S = 1 + 2 + \dots + (n - 1)

and

S = (n - 1) + \dots + 2 + 1

, so

2 S

(n - 1)

pairs each summing to

n

, giving

2 S = n (n - 1)

hence

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

. Both sorts generate this identical sum because pass

k

costs a decreasing

n - k

operations: selection scans

n - 1, n - 2, \dots, 1

remaining elements, and insertion (worst case) shifts

1, 2, \dots, n - 1

predecessors — the same triangular numbers in reverse order.

Why does a random array average about

\frac{n ( n - 1 )}{4}

inversions?

There are

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

pairs, and by symmetry each pair is equally likely to be in order or out of order, so each contributes probability

\frac{1}{2}

to being an inversion — summing gives

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

, exactly half the reverse-sorted maximum.

Why are bubble and insertion naturally stable while selection is not?

Bubble and insertion move elements only across adjacent out-of-order pairs, never jumping an equal key; selection's single long swap can, so it isn't stable by default.

Why can't any of these three break below

O (n^{2})

on worst-case general input?

They compare and move one adjacent-inversion's worth at a time, and worst-case inputs have

Θ (n^{2})

inversions — the general

O (n lo g n)

floor comes from the Lower Bound for Comparison Sorts, which these simple sorts don't reach.

Why is selection sort strictly worse than insertion on nearly-sorted data?

Insertion does

O (n)

work when inversions are few; selection still does its fixed

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

comparisons — so for tidy input insertion wins decisively.

Edge cases

Edge — What does insertion sort do on a length-0 or length-1 array?

Nothing meaningful: the loop over positions

1 \dots n - 1

never runs (or runs zero times), so it trivially returns the array as-is in

O (1)

Edge — On an already-sorted array, how many comparisons does insertion sort make?

Exactly

n - 1

— each element checks its single left neighbour, finds it not-greater, and stops immediately.

Edge — What happens to selection sort on an array where all elements are equal?

It still runs the full

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

comparisons but performs no reordering, since no element is ever strictly smaller than another — so the output is trivially the same array. This does not rescue its stability: instability is an inherent property of the abstract algorithm (its long-distance swap can hop equal keys), and it surfaces the moment equal keys are separated by a strictly smaller element.

Edge — On a reverse-sorted array of size

n

, how many inversions exist, and what does that mean for insertion sort?

Every pair is inverted, giving

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

inversions, so insertion sort performs the maximum number of shifts — its worst case.

Edge — If exactly one pair of adjacent elements is swapped in an otherwise-sorted array, how does insertion sort behave?

There's a single inversion, so insertion sort does one shift and

O (n)

comparisons — near-instant, showcasing its adaptivity.

Edge — Does the swap-flag optimisation help bubble sort on a reverse-sorted array?

No — every pass still finds swaps to make right up to the last, so the flag never triggers an early exit and the run stays

O (n^{2})

Recall One-line self-test

Cover this and recite: why does insertion sort win on nearly-sorted data? Reason ::: Its runtime is $Θ (n + inversions)$ — recall $Θ$ means the growth is pinned tightly to that expression — so when inversions are few it collapses to $O (n)$ , while selection's fixed scan and bubble's repeated sweeps cannot exploit the existing order.