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

Before you can read a single line of the parent note, you must own every symbol it throws at you without warning. This page builds each one from nothing — plain words, then a picture, then why the topic needs it. Read top to bottom; each block uses only what came before.

1. An array and its index

So $A[0]$ is the first box, $A[1]$ the second, and the last box in a row of $n$ boxes is $A[n-1]$.

Why the topic needs it: every sentence like "shift A[i] left" or "swap index 0 with index 1" is meaningless until you can point at exactly one box. The index is the finger you point with.

2. The size n

Why the topic needs it: we want to describe speed as the array grows. Saying "it took 3 comparisons" is useless on its own; saying "it took about $n^2$ comparisons" tells you what happens when $n$ becomes a thousand or a million. Every cost formula in the parent note is a recipe with $n$ as the ingredient.

3. Comparison < and swap

These are the only two moves a comparison sort is allowed. It may look at two values and ask which is bigger, and it may move values between boxes. Nothing else.

Why the topic needs it: the parent note counts comparisons and moves as its measure of work. To count them you must first agree that these — and only these — are the atomic actions. That is exactly the comparison-sort model, and it is what makes $O(n\log n)$ the wall these three sorts cannot beat.

4. The inversion — the star of the whole topic

Read the picture: draw an arrow from every box to every box on its right. Colour the arrow red if the left value is bigger (out of order) and green if it is fine. The red arrows are the inversions.

Why the topic needs it: this single count is the reason insertion sort wins. Each time insertion sort slides an element one box left, it flips exactly one red arrow to green. Nearly-sorted data starts with few red arrows, so insertion sort barely works. See Inversions and Counting for the deeper theory, and Stability in Sorting for what happens to equal values (which are never inversions — $A[i]>A[j]$ is strict).

5. Adding up $1+2+\cdots +(n-1)$

Every cost formula in the parent note ends in the same sum, so we must own it. The symbol $\sum$ (Greek capital "sigma", for Sum) is shorthand for "add up a list":

${\sum }_{k=1}^{n-1}k=1+2+3+\cdots +(n-1)$

Read it as: "let $k$ walk from $1$ up to $n-1$, and add every $k$ you land on."

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

Why the topic needs it: selection sort's scan on pass $i$ makes fewer comparisons each time — $n-1$, then $n-2$, down to $1$. Adding those up is this triangle. Same story for bubble's worst case and insertion's worst case. Knowing the sum is $\frac{n(n-1)}{2}$ is knowing why all three are quadratic.

6. What "$O(n^2)$" actually says

Watch it happen to our triangle: $\frac{n(n-1)}{2}=\frac{n^2-n}{2}=\underset{\text{dominates}}{\underbrace{\frac{1}{2}{n}^2}}-\underset{\text{tiny for big }n}{\underbrace{\frac{1}{2}n}}$

For $n=1000$ the first piece is $500,000$ and the second is only $500$ — the $n^2$ term drowns everything. So we call it $O(n^2)$.

Why the topic needs it: "these three are all $O(n^2)$" and "insertion drops to $O(n)$ when nearly sorted" are the parent note's two headline claims — both are statements in this language.

7. Best / worst / average case

Why the topic needs it: Big-O alone hides the punchline. Bubble and insertion share the worst case $O(n^2)$, yet insertion has a best case of $O(n)$ that bubble-with-a-flag matches but selection can never reach. The whole "when insertion wins" argument lives entirely in the gap between best and worst. This adaptiveness is why real libraries — Timsort, Introsort — drop to insertion sort for tiny chunks before handing off to Merge Sort or Quicksort.

Prerequisite map

Read it top-down: boxes and indices let you point; pointing lets you compare and swap; comparing defines the inversion; the triangle sum plus Big-O turn counts into growth shapes; and inversions + cases together explain the winner.

Equipment checklist

Cover the right side and answer each aloud. If any stumps you, re-read that section before opening the parent note.