Sorting Algorithm Explorer

Watch 12 sorting algorithms work on the same data, race two side by side and count comparisons, writes and remaining inversions.

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 n

so 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.
Inversions remaining (unsortedness) during the run
Cumulative comparisons and writes
Measured comparisons versus n (Run scaling)
Comparisons per element versus n