Sorting Algorithm Race

step through two algorithms racing on the same input — comparisons, swaps, complexity

Loading interactive simulation...

big-O is not the whole story 🖖

Bubble sort makes exactly n(n−1)/2 comparisons in the worst case — about 2,000 for n=64. Every pass must scan the full remaining unsorted region with no early escape. Quicksort's partition places the pivot in its final slot and splits the problem into two sub-problems; each level of recursion does O(n) work over O(log n) levels, giving O(n log n) total. The catch: if the pivot always lands at one end — for example, sorted input with a last-element pivot — partitioning degrades to n sub-problems of size n−1, n−2, ... summing to O(n²). The mid-element pivot used here avoids that, which is why reversed input stays fast. Few-unique values are the interesting case: when many elements equal the pivot, swapping identical values wastes work and can push towards quadratic. Big-O tells you the growth class; constants, input sensitivity, and cache behavior determine which algorithm you actually ship.

Why it counts steps, not seconds 🖖

This race scores each algorithm by counting comparisons and swaps, not with a stopwatch. Wall-clock time depends on your CPU, your browser, and whatever else is running, so the same code can look fast or slow on different machines. Counting operations gives a clean, reproducible measure of the actual work done: the same input always yields the same counts, letting you compare the algorithms themselves and not the hardware.

Quicksort was born translating Russian 🖖

Tony Hoare invented quicksort in 1959 as a visiting student in Moscow, working on a machine-translation project. To look up a Russian sentence in a dictionary, he first had to put its words in alphabetical order — and the standard method was hopelessly slow. His fix, partitioning around a pivot, became one of the most-used algorithms ever written. The bars you watch race here trace an idea that started as a language problem, not a computing one.

Problem solved in full

Predicting bubble sort's swap count exactly on 64 reversed elements 7 steps
Run the race on the reversed preset — 64 elements, largest first. Predict bubble sort's swap count exactly, not its order of growth; then say what stops any neighbour-swapping algorithm from beating it.
1. An inversion is a pair standing in the wrong relative order. Reversed input is the extreme: for every i < j the earlier element is the larger one, so every pair is inverted and the count is all of them. Get this number before anything moves — it turns out to be the entire problem.
  
  $I = # {(i, j) : i < j, a_{i} > a_{j}} = (2 64) = \frac{64 \times 63}{2} = 2, 016$
2. Bubble sort exchanges neighbours only, and only when they are out of order. Such an exchange repairs that one pair and disturbs no other, because the two elements that move keep the same relationship to everything outside them. One swap, one inversion — never two, never none.
  
  $a_{k} > a_{k + 1} ⟶ I \mapsto I - 1$
3. Sorted means zero inversions. Starting at 2,016 and removing exactly one per swap leaves no room to manoeuvre: the swap count is forced. The panel prints 2,016 swaps, and that is an identity rather than a worst-case bound.
  
  $S = I_{0} - 0 = 2, 016$
4. Comparisons are a separate count that happens to coincide here. Pass i scans j = 0 … 62 − i, so the total is 63 + 62 + ⋯ + 1 — the same 2,016 the bubble worst case n(n−1)/2 row shows. Equal counts mean every single comparison found an inversion, which is what "worst case" means here. The counter under each panel’s title counts one step per comparison plus one per swap, so it reads step 0 / 4,032 before you start, and the › button consumes exactly one of those steps per click. The O(n²) beside the title is a label, not a tally.
  
  $C = i = 0 \sum 62 (63 - i) = 63 + 62 + \dots + 1 = \frac{63 \times 64}{2} = 2, 016 = \frac{n ( n - 1 )}{2}, C + S = 4, 032$
5. Now generalise step 2, because this is what quicksort exploits. Exchanging two entries d places apart leaves every pair formed with an element outside the span alone in total: such an element is re-compared against the other end, the two comparisons trade places, and its contribution is unchanged. What can move is the pair itself, plus the 2(d − 1) pairs each end forms with the d − 1 entries in between. At most 2d − 1 inversions can die per exchange, and setting d = 1 gives back the single inversion of step 2.
  
  $1 + 2 (d - 1) = 2 d - 1 (d = 1 \Rightarrow 1)$
6. Quicksort's first partition takes the middle element as pivot, a[31] = 33, and exchanges (0, 63), (1, 62), … , (31, 32) — 32 exchanges at distances 63, 61, … , 1. Step 5 caps their combined effect at 2,016 inversions, and that single pass leaves the array completely sorted, so exactly 2,016 were removed. The cap is met with equality: every one of the 32 exchanges achieved its own maximum.
  
  $p = a_{31} = 33, d = 63, 61, \dots, 1 : m = 1 \sum 32 (2 (2 m - 1) - 1) = m = 1 \sum 32 (4 m - 3) = 2, 112 - 96 = 2, 016$
7. So the two algorithms are not competing on cleverness, they are competing on reach. Quicksort's printed 334 comparisons and 64 swaps sum to the 398 on its counter — and only 32 of those swaps move anything, the other 32 being the pivot exchanged with itself in stretches that are already in order. Its 334 also comes in under the printed n·log₂n reference of 384, because the middle element of a reversed run is its median, so every split is even.
  
  $334 + 64 = 398, 64 lo g_{2} 64 = 384, \frac{2 , 016}{32} = 63$
Answer

2,016 swaps and 2,016 comparisons — the 4,032 steps on the counter. And 2,016 is not a fact about bubble sort: it is a floor for a whole family. Any algorithm restricted to exchanging adjacent elements — insertion sort, cocktail shaker, gnome sort, or one nobody has written yet — deletes at most one inversion per swap by step 2, so all of them need at least 2,016 swaps on this input and all of them are Ω(n²) on reversed data because of the model they work in, not because they are clumsy. Quicksort escapes that floor by being allowed to move an element 63 places at once: 2,016 inversions cleared by 32 real exchanges is 63 inversions per exchange, and step 5 says that is the most any single exchange over that distance could have managed. The panel computes neither the inversion count nor the lower bound it implies.

$S \geq I_{0} = (2 64) = 2, 016 (d = 1), \frac{I _{0}}{32} = 63$

Learning path

Counting work, not seconds

Leads to recursion-tree

References (1)

Insight block 3 — quicksort as its author published it: C. A. R. Hoare, "Quicksort." The Computer Journal 5(1), 10–16, 1962. The algorithm first appeared the year before as C. A. R. Hoare, "Algorithm 64: Quicksort", Communications of the ACM 4(7), 321, 1961.

By the 42Math team · Updated 2026-05-27

Reviewed against published sources. Corrections welcome. Editorial policy · Corrections

All Computing lessons →

Example problems

nearly sorted - Input distribution changes relative algorithm efficiency.
reversed - Bubble sort makes 2,016 comparisons and 2,016 swaps: every single comparison finds its pair out of order, because reversing 64 elements inverts all 2,016 pairs at once. Quicksort settles it in 334 comparisons and 64 swaps, under its own n·log₂n reference of 384, since the middle element of a reversed array is exactly the median every time it partitions.
few unique - Eighty elements drawn from only eight distinct values. Quicksort needs 534 comparisons against its n·log₂n reference of 506, the only one of the three presets where it ends up above its own line: elements equal to the pivot get swapped and nothing is gained by it. Bubble sort still makes its fixed 3,160 comparisons and only 1,330 swaps, because so many neighbouring pairs already match.