Presets
Playback
Algorithms
Lane A is the top picture, lane B the bottom one in race mode.
Data
Initial order of the values.
Run
Number of elements and operations per second.
Layers
Model checks
The science
What a comparison sort can and cannot do
Every algorithm here except radix and counting sort learns about the data only by comparing two elements. A decision tree that tells all n! orderings apart needs at least log2(n!) comparisons in the worst case:
Cmin(n) = ⌈log2 n!⌉ ≈ n log2 n − 1.443 nso no comparison sort can be asymptotically faster than O(n log n). Merge sort comes within a few percent of this bound (worst case n⌈log2n⌉ − 2⌈log2n⌉ + 1), heap sort and quicksort a little further. Radix and counting sort escape the bound because they use the values as array indices.
Typical costs
- Bubble, cocktail, selection, insertion: about n²/2 comparisons. Insertion sort on a reversed array needs exactly n(n−1)/2; on a nearly sorted array only about n.
- Shell sort: insertion sort over shrinking gaps (Ciura's sequence); roughly n1.2 to n1.3 in practice, not proven.
- Merge sort: O(n log n) always, stable, needs O(n) extra memory.
- Quicksort: O(n log n) on average (about 1.39 n log2 n comparisons for random pivots) but O(n²) if the pivot is always the smallest or largest element, which the last-element pivot does on sorted input.
- Heap sort: O(n log n) always, in place, not stable, poor cache locality.
- Comb sort: bubble sort with a shrinking gap (factor 1.3).
- Radix (LSD, base 10) and counting sort: O(n·d) and O(n + k), no comparisons, so the comparison counter stays at zero; writes are counted.
What the counters mean
Comparisons counts every evaluation of a < b on two array values. Writes counts every store into the array (a swap is two writes). Inversions is the number of pairs that are out of order, the natural measure of unsortedness; a sort finishes when it reaches zero.
Honest limits
Counts are exact for the code shown, but real running time also depends on caches, branch prediction and the language runtime, which are not modelled. The animation speed is a display choice, not a speed measurement. Sound maps the value being touched to a pitch and is off by default.
What to try
- Race Insertion against Merge on Nearly sorted data: insertion wins. Switch to Reversed and it loses badly.
- Run quicksort on Already sorted data and watch the comparison count explode (last-element pivot).
- Use Run scaling to measure comparisons for n = 16 to 512 and see the n² and n log n curves separate.
- Pick Radix: no comparisons at all, only writes.
- Turn on sound to hear the structure of each algorithm.