The idea: race two sorts on one array
The page builds one array and gives each panel its own copy. Pick a sort for each side and press Race. Both sorts then run at the same time: every step of the animation is one comparison on the left and one on the right, together with everything that comparison caused (a swap, a shift, a value copied back from the buffer). After step k both sides have compared k pairs, so the bars show how far each sort got for the same amount of comparing. A side that finishes turns green and waits.
Big or badly ordered arrays take hundreds of comparisons. The comparisons/step option (1, 4 or 16) groups several into one step; the narration then describes the last one.
What is counted
- Comparisons: two keys compared. This is the unit of a step, and the grey bar under each panel. Its two ticks mark n·log₂n and n(n−1)/2.
- Writes: one value stored into the array or into the merge buffer. A swap is 2 writes. A single temporary variable (insertion sort's key, the swap temporary) is not counted. A swap of a slot with itself is skipped.
- Swaps: exchanges of two slots, for the sorts that swap.
Reading a panel
Bar height is the value. A bar is red while it is being compared, orange when it is the pivot, the key being inserted or the current minimum, and purple right after it was written. The thin strip under the bars shows each sort's own structure (its legend is under the panel):
| Sort | The strip shows | Below the strip |
|---|---|---|
| Bubble | the sorted suffix that grows from the right | — |
| Insertion | the sorted prefix | the key, under the hole it will fill |
| Selection | the sorted prefix (final); the current minimum is orange | — |
| Shell | the chain of every h-th value being insertion-sorted, for the current gap h | the key |
| Heap | the max-heap and the sorted suffix behind it | — |
| Quick | the partition range: ≤ pivot, > pivot, unscanned; pivots already placed; the call depth is in the line above the bars | — |
| Merge | the left and right run being merged | the buffer: a copy of both runs, greyed out as values are taken back |
| TimSort | the runs on the run stack, then the two runs being merged | the buffer (a copy of the left run) or the key |
The sorts and their numbers
| Sort | Comparisons: best / typical / worst | Writes | Stable |
|---|---|---|---|
| Bubble (stops after a pass with no swap) | n−1 (sorted) / ≈ n²/2 / n(n−1)/2 | 2 per inversion | yes |
| Insertion | n−1 (sorted) / ≈ n²/4 / n(n−1)/2 | 1 per inversion, +1 per key that moves | yes |
| Selection | n(n−1)/2 always | at most n−1 swaps | no |
| Shell (Knuth's gaps 1, 4, 13, 40) | about n1.25 to n1.5 | like insertion, but far fewer | no |
| Heap | ≈ 2·n·log₂n on any input | ≈ n·log₂n swaps | no |
| Quick, last element as pivot (Lomuto) | ≈ 1.39·n·log₂n / n(n−1)/2 on sorted or reversed input | few swaps | no |
| Quick, median of 3 | ≈ n·log₂n on sorted input too | few swaps | no |
| Merge (top-down) | ≈ ½·n·log₂n (sorted) / at most n⌈log₂n⌉ − n + 1 | 2·n per level (copy out, copy back) | yes |
| TimSort (simplified) | n−1 (sorted) / fewer than merge sort when the input has runs | only the left run is copied to the buffer | yes |
What the demos show
| Demo | Result | Why |
|---|---|---|
| insertion vs quick, nearly sorted (32) | insertion 47 comparisons, quick 383 | Insertion pays about n + inversions, and there are only a few. Quick's last-element pivot is almost always the largest value left, so each partition peels off one value. |
| quick vs merge, already sorted (32) | quick 496 = 32·31/2, merge 80 | The worst case of a last-element pivot. Merge sort stops each merge as soon as the left run runs out: 16 comparisons per level, 5 levels. |
| heap vs merge, random (32) | heap 225, merge 121 | Heap sort makes two comparisons per level of every sift-down. Merge sort stays under its bound of 129. |
| bubble vs insertion, random (24) | bubble 266, insertion 158 | Both remove one inversion per move, but bubble sort keeps re-comparing the part that is already in order. |
| TimSort vs merge, sorted runs (48) | TimSort 139, merge 185 | TimSort finds the four runs (reversing the descending one) and merges only those. Merge sort splits blindly in half. |
| selection vs insertion, writes (32) | selection 496 comparisons but 30 swaps (60 writes); insertion 206 comparisons but 202 writes | Selection sort moves each value at most once; insertion sort moves a value one slot per inversion. |
| stability, merge vs heap (16, few unique) | merge keeps every a, b, c, d in order; heap swaps 15 pairs of equal keys | Merge sort takes from the left run on ties. Heap sort's swaps jump over equal keys. |
| last pivot vs median of 3, sorted (48) | 1128 = 48·47/2 against 231 | The median of the first, middle and last value is the true middle of a sorted range. |
The inputs
Values are 5 to 99, built from a seeded generator: the same input, n and seed always give the same array. Random, already sorted and reversed use distinct values. Nearly sorted is sorted, then n/8 swaps of values at most 3 apart. Few unique values uses only 20, 45, 70 and 95. Sorted runs is four runs of about n/4 values, the second one descending.
Stability
A sort is stable if equal keys keep their input order. It matters when you sort records by one field after another, for example by name and then by city. With few unique values each copy of a key gets a colour and a letter in input order (a, b, c, …). When a sort finishes, the line under its panel says whether every a still comes before its b. Bubble, insertion, merge and TimSort never jump a value over an equal one. Selection, Shell, heap and quick sort swap over long distances and can (Demo: stability, merge vs heap).
Quick sort with a Lomuto partition also does badly on few unique values: all keys equal to the pivot go to one side, so the splits are uneven.
Comparisons are not the whole cost
Comparisons are a fair, machine-independent count, which is why the page steps on them. Real running time also depends on writes and on memory access. Merge sort copies every value out and back on every level, while quick sort works in place in the cache. That is why a well-tuned quick sort usually beats merge sort in practice despite more comparisons (see Quick Sort vs Merge Sort, which measures it). Writes matter most when they are expensive, as on flash memory: there selection sort's n−1 swaps can be worth its n²/2 comparisons.
What the page leaves out
- TimSort is simplified. minrun is fixed at 8 so that runs are visible on 48 values (CPython picks 32 to 64, so on fewer than 64 values the real TimSort is just one binary insertion sort). There is no galloping mode, and the left run is always the one copied to the buffer. The run-stack merge rules are the real ones. The TimSort page shows galloping.
- Quick sort recurses into the left side first; real implementations recurse into the smaller side, switch to insertion sort on small ranges and fall back to heap sort (introsort).
- Non-comparison sorts such as counting sort and radix sort make no comparisons at all, so they cannot race on this axis.
- Running time in milliseconds and cache effects.
See also Comparison Sorting (one sort at a time, with code), Heap Sort (the heap drawn as a tree), TimSort and Quick Sort vs Merge Sort (memory and measured time).