The Sound Of Sorting
Four algorithms doing the same job, with their comparison counts checked against the theory that predicts them.
What it is
A hundred and twenty shuffled bars, sorted four different ways. Pitch follows whichever value is being touched, so each algorithm has a characteristic sound: bubble sort’s rising sweeps, merge sort’s interleaved runs, quicksort’s sudden scattering.
The counter is the point. Watch it while switching algorithms.
How it works
Each algorithm yields a stream of events, compare and swap and set, rather than simply sorting. The animation replays that stream, and the same events increment the counters. So the number on screen isn’t an estimate of the work, it is the work, counted by the code that’s drawing it.
That structure buys a test worth having. Replaying an algorithm’s event list onto a copy of the input has to produce a sorted array, which means the visualisation can’t drift from what the algorithm actually did. An animation that looks right while lying about the operations would pass a weaker test easily.
Blips are scheduled against the audio clock rather than fired on frames, and dropped if they’d fall too far ahead. Otherwise a fast algorithm queues thousands of oscillators and the sound lags seconds behind the picture.
What surprised me
The theory is almost embarrassingly accurate.
Comparisons at n = 512, from the same shuffle:
| algorithm | comparisons | textbook |
|---|---|---|
| bubble | 129,781 | n²/2 = 131,072 |
| insertion | 66,206 | n²/4 = 65,536 |
| merge | 3,959 | n log₂n = 4,608 |
| quick | 5,016 | ~1.39 n log₂n = 6,402 |
Bubble sort is within 1% of n²/2 and insertion within 1% of n²/4. I expected the asymptotic forms to be in the right area, not to nail it at a size small enough to animate.
Merge sort undershooting n log₂n was the one I had to go and check. It isn’t an error. When one half of a merge is exhausted, the remaining elements get copied across with no comparisons at all. The textbook figure is the upper bound and the saving is real, about 14% here.
And the headline: bubble sort does 33 times the comparisons of merge sort on 512 items. At 512. The gap grows without limit, and this is the smallest scale at which anyone would bother to look.
What I would do next
Add a nearly-sorted input, where insertion sort goes near-linear and beats quicksort outright. That’s the case that keeps it in real libraries.