Sorting

Sorting is a 60-year-old problem that still shows up in almost every program you write — not because you call sort() constantly, but because half the other algorithms you rely on assume their input is sorted. Binary search, shortest-path relaxations, interval merging, median-finding, deduplication by adjacency, and every query plan that claims "this index is ordered" all rest on the same primitive. Getting it right (and knowing when you're paying too much for it) compounds through the rest of the curriculum.

Five classic sorts, one shuffled array. Watching them move answers more questions than reading about them — the playground on the next tab races bubble, insertion, selection, quicksort, and mergesort side-by-side so you can see why "O(n²) vs O(n log n)" actually matters.

Analogy

Imagine a shelf of books in random order. Five librarians each pick a different strategy:

• Bubble walks the shelf pairwise, swapping adjacent books every time the left one is out of order. Repeats until a full pass is clean. Slow but simple.
• Insertion treats the leftmost chunk as "already sorted" and slides each new book left until it finds its spot. Great on nearly-sorted shelves.
• Selection scans the unsorted part for the absolute smallest book and swaps it to the boundary. Predictable but unchanging — always the same work regardless of input.
• Quicksort grabs one book as a pivot, pushes smaller ones left and larger ones right, then recursively sorts each half. Fast on average, wobbly on worst case.
• Mergesort splits the shelf in half, sorts each half independently, then merges them back in order. Predictable performance, but needs scratch space.

Each librarian finishes with the same sorted shelf; the interesting question is what they paid to get there.

The core measure: comparisons and swaps

Every sort is really a sequence of two primitive operations:

• Compare — "is a[i] less than a[j]?"
• Swap — "exchange a[i] and a[j]."

Counting those operations (and how they scale with the array size n) is how we compare algorithms. The table below is what every algorithms textbook opens with — and what every CS interview eventually asks you to reproduce on a whiteboard.

	Best	Average	Worst	Stable?	In-place?
Bubble	O(n)	O(n²)	O(n²)	yes	yes
Insertion	O(n)	O(n²)	O(n²)	yes	yes
Selection	O(n²)	O(n²)	O(n²)	no	yes
Quicksort	O(n log n)	O(n log n)	O(n²)	no	yes
Mergesort	O(n log n)	O(n log n)	O(n log n)	yes	no

Stable means equal-keyed elements keep their relative order. That matters whenever sort is the second stage of a multi-key sort: to sort people by last name and then by first name, you stable-sort on first name, then stable-sort on last name, and the composition works. Unstable sorts silently eat that property.

In-place means the sort uses only O(1) or O(log n) extra space — no second array the size of the input.

Tracing bubble sort by hand

Take [5, 2, 4, 1, 3]. One full pass of bubble:

1. Compare 5, 2 → out of order → swap → [2, 5, 4, 1, 3]
2. Compare 5, 4 → swap → [2, 4, 5, 1, 3]
3. Compare 5, 1 → swap → [2, 4, 1, 5, 3]
4. Compare 5, 3 → swap → [2, 4, 1, 3, 5]

After one pass, the largest element is guaranteed to be at the end. That's why bubble needs up to n passes — the largest un-placed element floats up one slot per pass. Four passes on a five-element array = up to 4×4 = 16 comparisons and as many as 10 swaps. You can do this by hand in a minute; if the count surprises you, that's the point of the level.

Why bubble sort's swap count equals the inversion count

An inversion is any pair (i, j) where i < j but arr[i] > arr[j]. Bubble sort only ever swaps adjacent out-of-order pairs — and every such swap fixes exactly one inversion. So the total number of swaps bubble sort performs before it's sorted equals the inversion count of the input.

That identity turns "how many swaps will bubble make on [3, 1, 4, 1, 5, 9, 2, 6]?" into a pure counting problem — no simulation needed. The challenge on this level asks you to do that count.

When quicksort and mergesort diverge from O(n log n)

The divide-and-conquer sorts are built around halving the problem repeatedly, which is what the log n factor encodes. They diverge from that ideal when the split becomes unbalanced:

• Quicksort hits O(n²) when the pivot is the worst possible choice every time (e.g. always the already-sorted max, on an already-sorted input). Randomised or median-of-three pivots fix this in practice.
• Mergesort never degrades — every merge is guaranteed O(n) work and there are always log₂(n) levels — but it pays for that guarantee with an auxiliary array.

What real standard libraries actually ship

No serious standard library ships a textbook sort. Every modern runtime uses a hybrid that starts with a divide-and-conquer but falls back to insertion sort on small sub-arrays (insertion is brutally efficient at n ≤ 16 or so due to cache friendliness and low constants):

Language	sort() default	Notes
JavaScript (V8)	TimSort	Hybrid mergesort + insertion. Stable. Same family as Python.
Python	TimSort	Designed by Tim Peters, explicitly optimized for real-world mostly-sorted data. Stable.
Java — objects	TimSort	Arrays.sort on Object[] preserves stability.
Java — primitives	Dual-pivot quicksort	Unstable (doesn't matter for primitives) but faster than classic single-pivot.
C++ (std::sort)	Introsort	Quicksort that watches recursion depth; falls back to heapsort when depth exceeds 2·log₂(n) to bound worst case.
Go (sort.Slice)	pdqsort	"Pattern-defeating" quicksort — detects adversarial patterns and mitigates O(n²) risk.
Rust	TimSort-derivative	Stable; sort_unstable exists for pdqsort.

The takeaway: every shipping sort is ~95% divide-and-conquer and ~5% insertion sort glued together. Raw textbook sorts basically never appear in production code; they appear in the bugs of production code.

Picking the right sort in practice

Nobody wakes up and chooses bubble. But the shape of the problem does change which algorithm you'd reach for:

• Data is mostly sorted, small drift: insertion or TimSort. Linear-time on the common case.
• Data is huge and doesn't fit in memory: mergesort. The merge step is inherently streamable; you can merge N pre-sorted files without ever holding more than one block of each in memory. External sorts are why mergesort never goes obsolete.
• Stability matters (multi-key sort): mergesort or TimSort. Never selection or standard quicksort.
• In-place is mandatory (embedded, GPU memory): quicksort or heapsort. Mergesort's O(n) aux array kills it.
• Input is adversarial / untrusted: randomised-pivot quicksort or introsort. Deterministic-pivot quicksort on user-controlled input is a denial-of-service vector.

Common gotchas

• Bubble sort has an undeserved bad rap. On an already-sorted array with an early-exit flag, bubble finishes in O(n) and does zero swaps. The reason it's still a meme is that real-world inputs are almost never already sorted — but teaching bubble without the early-exit optimization gives it a worse reputation than it deserves.
• "My quicksort is slow" is almost always pivot choice. Median-of-three (first/middle/last) is the 30-second fix.
• Stability is a footgun when you didn't know you needed it. If you sort a list of (name, score) by name using an unstable sort and the scores were pre-sorted by a previous pass, the scores are now scrambled within each name bucket. This bug is completely silent and surfaces weeks later as "the report's order is wrong".
• Array.prototype.sort in JS without a comparator converts elements to strings. [10, 9, 1].sort() returns [1, 10, 9] because "10" < "9" lexically. Always pass a comparator.

Playground

Pick an algorithm, press play, watch the bars. Each frame highlights the two indices being compared in var(--color-accent). Swaps flash briefly in var(--color-success). The counters update every step.

Try the same input with each algorithm and compare. Then turn off the shuffle and re-run on an already-sorted array: bubble and insertion finish in one linear pass, selection still does its full O(n²) scan, quicksort degrades to its worst case, mergesort stays solidly O(n log n).

Visualizer

The Complexity Curves panel plots n², n log n, and n against each other as n grows — a picture of why the lesson matters. At small n (say, 10), all three look similar. At n = 1000 the quadratic curve has already run off the top of the chart.