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

WHY are these all $O(n^2)$ ? (Derivation from scratch)

WHAT we count: the number of comparisons + the number of element moves, as a function of input size $n$ .

Selection sort — exact count (always the same)

HOW it runs: for each position $i$ from $0$ to $n-2$ , scan the rest to find the minimum.

Pass $i=0$ : compare against $n-1$ elements.
Pass $i=1$ : compare against $n-2$ elements.
… down to the last pass: $1$ comparison.

Total comparisons: $C = (n-1) + (n-2) + \dots + 1 = \sum_{k=1}^{n-1} k = \frac{(n-1)n}{2}$

Why this sum? The Gauss trick: pair the first and last term $(n-1)+1=n$ , second and second-last $(n-2)+2=n$ … there are $\frac{n-1}{2}$ such pairs each summing to $n$ , giving $\frac{n(n-1)}{2}$ .

Because the scan never stops early, $C=\frac{n(n-1)}{2}=O(n^2)$ in best, worst, and average cases. Swaps, however, are at most $n-1$ (one per pass) — selection sort minimises writes.

Bubble sort — worst case

HOW: repeatedly pass through the array swapping adjacent inversions. After pass $k$ , the largest $k$ elements are locked at the end.

Worst case (reverse-sorted): pass $k$ does $n-k$ comparisons: $C = \sum_{k=1}^{n-1}(n-k) = \frac{n(n-1)}{2} = O(n^2)$

With a "did I swap?" flag, best case (already sorted) = ==one pass, $n-1$ comparisons, $O(n)$ == — but it does many swaps in the worst case ( $O(n^2)$ ).

Insertion sort — best vs worst

HOW: keep a sorted prefix A[0..i-1]. Take A[i], shift larger elements right, drop it in.

Best case (already sorted): each new element is $\geq$ its left neighbour, so the inner loop stops immediately → $1$ comparison per element → $n-1$ comparisons → == $O(n)$ ==.
Worst case (reverse-sorted): element $i$ shifts past all $i$ predecessors: $C = \sum_{i=1}^{n-1} i = \frac{n(n-1)}{2} = O(n^2)$

The number of moves equals the number of inversions in the array — this is the deep reason insertion sort is fast on nearly-sorted data.

Formula Cost summary

	Comparisons (best / avg / worst)	Swaps/Moves (worst)	Stable?
Bubble (w/ flag)	$n-1$ / $O(n^2)$ / $\frac{n(n-1)}{2}$	$O(n^2)$	✅
Selection	$\frac{n(n-1)}{2}$ always	$n-1$	❌ (default)
Insertion	$n-1$ / $O(n^2)$ / $\frac{n(n-1)}{2}$	$O(n^2)$ but $\Theta(\text{inversions})$	✅

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

Worked examples

Common mistake Steel-manning the wrong ideas

❌ "Bubble and insertion are both $O(n^2)$ , so they're equally fast." Why it feels right: same Big-O worst case. The fix: Big-O hides the best/average behaviour and the constant factors. Insertion does far fewer moves on average and is the standard "small-array" sort inside real libraries (e.g. Timsort, introsort fall back to insertion for tiny chunks). Bubble is almost never used in practice.

❌ "Selection sort is fast because it does few swaps." Why it feels right: only $n-1$ swaps — true and useful when writes are expensive (e.g. flash memory). The fix: it still does $\frac{n(n-1)}{2}$ comparisons every time, so on nearly-sorted data it's strictly worse than insertion.

❌ "Selection sort is stable." Why it feels right: it looks gentle. The fix: swapping a distant minimum into place can jump it past an equal key, breaking stability. Insertion and bubble (shift, don't long-swap) are naturally stable.

❌ "Insertion is $O(n)$ because the inner loop sometimes stops early." The fix: only in the best/near-sorted case. Reverse-sorted input forces full shifts → $O(n^2)$ .

Recall Feynman: explain to a 12-year-old

Imagine sorting playing cards in your hand.

Insertion: you pick up cards one at a time and slide each into the right place among the cards you're already holding. If they were almost in order, you barely move anything — super quick!
Selection: you look at all the cards on the table, find the smallest, place it, then look at all the rest again, find the next smallest… You always look at everything, even if they were already sorted.
Bubble: you keep swapping any two neighbours that are in the wrong order, sweeping left to right, until nothing needs swapping. The big cards slowly "float" to the end. The trick: insertion sort is lazy in a good way — it stops the moment a card is already in place. That's why it wins when things are nearly tidy.

#flashcards/coding

Why is selection sort always

\Theta(n^2)

even on a sorted array?

Its inner scan to find the minimum never stops early — it always makes

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

comparisons regardless of input order.

What is the best-case time of insertion sort and when does it occur?

O(n)

, when the array is already (nearly) sorted — each element only checks its left neighbour and stops.

Insertion sort's number of moves equals what quantity?

The number of inversions in the array (out-of-order pairs).

Which two of the three sorts are naturally stable?

Bubble and insertion (they shift adjacent elements); selection is not stable by default.

Which sort minimises the number of writes/swaps, and why might that matter?

Selection sort — only

n-1

swaps. Useful when writes are expensive (e.g. flash memory wear).

When does insertion sort beat bubble and selection in practice?

On small or nearly-sorted arrays — it's adaptive, so libraries use it for tiny sub-arrays inside faster sorts.

Derive selection sort's comparison count.

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

by Gauss pairing.

What single optimisation makes bubble sort

O(n)

in the best case?

A "swapped?" flag: if a full pass makes no swaps, the array is sorted — stop.

Reverse-sorted input: how many comparisons does insertion sort do?

\sum_{i=1}^{n-1} i = \frac{n(n-1)}{2}

, its worst case

O(n^2)

Why is bubble sort rarely used despite the same Big-O as insertion?

It does far more swaps on average and no real advantage; insertion has better constants and is the standard small-array sort.

Connections

Merge Sort — $O(n\log n)$ divide-and-conquer; uses insertion sort for small chunks.
Quicksort / Introsort — switch to insertion sort below a size threshold.
Timsort — real-world hybrid built on insertion sort + merge, exploits existing runs.
Inversions and Counting — formal measure of "how unsorted" an array is.
Big-O Notation — why best/average/worst all matter beyond worst-case.
Stability in Sorting — preserving order of equal keys.
Lower Bound for Comparison Sorts — the $\Omega(n\log n)$ barrier these quadratic sorts don't beat.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho yaar, teen sorting algorithms hain aur teeno ka worst case $O(n^2)$ hai — par inka "personality" alag hai. Selection sort har pass me poori unsorted list ko ghoorta hai minimum dhoondhne ke liye, chahe array pehle se sorted ho ya na ho — isliye comparisons hamesha $\frac{n(n-1)}{2}$ hi rehte hain, koi shortcut nahi. Bubble sort bagal wale (adjacent) elements ko swap karta rehta hai, bade elements aage "float" karte hain; ek flag laga do toh best case me $O(n)$ ho jaata hai. Insertion sort taash ke patte sort karne jaisa hai — naya element uthao aur apni sorted line me sahi jagah slide karke daal do, aur jaise hi chhota element mil jaaye, ruk jao.

Asli magic insertion sort me yahi "ruk jao" waali baat hai. Jab array almost sorted ho, toh har element bas apne left neighbour se compare hota hai aur turant settle ho jaata hai — total kaam sirf $O(n)$ . Technically, insertion sort jitne inversions (ulte pairs) honge utna hi kaam karta hai. Sorted array me 0 inversions → bijli ki speed. Yeh adaptiveness hi reason hai ki real libraries (Timsort, introsort) chhote chunks ke liye insertion sort use karti hain.

Ek common galti: "dono $O(n^2)$ hain toh equal fast honge" — galat! Big-O sirf worst case batata hai, average behaviour aur constants chhupa deta hai. Practice me insertion sort kam moves karta hai aur nearly-sorted data pe selection se kaafi tej hai. Doosri galti: "selection sort stable hai" — nahi, kyunki door se minimum ko swap karne se equal keys ka order bigad jaata hai. Insertion aur bubble stable hote hain kyunki woh shift karte hain, lambi jump nahi maarte.

Toh yaad rakho: chhote ya nearly-sorted data pe insertion sort jeetta hai kyunki woh aalsi hai par acche tareeke se — jaisे hi kaam khatam, ruk jaata hai. Selection sort bas tab kaam ka hai jab writes mehengi ho (kam swaps), warna insertion is the practical champion.

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

WHY are these all $O(n^2)$ ? (Derivation from scratch)

Selection sort — exact count (always the same)

Bubble sort — worst case

Insertion sort — best vs worst

The key insight: inversions

Worked examples

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Sorting & Searching

Connections