Sorting is the problem civilization solved first and computers solve most. A library, a census, a dictionary, a deck of cards being readied for a deal — all are answers to a single question: how do you put a pile of things in order so that any one of them can be found again? Knuth gave the whole of the third volume of The Art of Computer Programming to sorting and searching, more than seven hundred pages, and confessed he could have written more. It looks like the most mundane task in computing. It is, in fact, a menagerie of wildly different creatures, each with its own temperament — and if you give each one a voice, you can hear them apart with your eyes closed.
That is the trick of this room. We map each number in the array to a pitch — low values low, high values high — and sound a note every time an algorithm looks at or moves an element. Suddenly the abstract becomes music. Bubble sort, plodding through neighbour after neighbour, drones in a low, grinding groan that climbs by agonizing half-steps. Quicksort tears the array into pieces with a burst of scattered notes and then, as each piece falls into place, resolves without warning into a clean ascending scale. You are not hearing a metaphor. You are hearing the algorithm's control flow, played as it runs.
"An algorithm's shape has a sound. Order emerging from disorder is, quite literally, a scale being played — and every method plays it in a different voice." — after the sorting-sonification tradition, T. Bingmann & others
I · Comparisons & the n·log·n WallWhat sorting costs
Every comparison sort works by asking one kind of question — "is this one bigger than that one?" — and rearranging accordingly. Knuth's central measure of a sort is therefore the number of comparisons it makes. The naïve methods — bubble, insertion, selection — make about n²/2 of them: double the input and the work quadruples. The clever ones — merge, quick, heap — make about n·log₂n: double the input and the work barely more than doubles. On a thousand elements that is the difference between half a million comparisons and ten thousand. The instrument below lets you watch and hear that gulf open in real time.
And there is a floor no comparison sort can break through. To distinguish which of the n! possible orderings you were handed, you need enough yes/no answers to tell them apart, and that is log₂(n!) ≈ n·log₂n comparisons at minimum. Knuth proves it in §5.3.1: merge sort and heapsort already stand essentially on that theoretical floor. You cannot sort by comparison meaningfully faster. Press play, choose a voice, and listen to the bound.
Each bar is a number; its height and its pitch are the same value. A comparison lights two bars and sounds a note; a swap moves them. The naïve sorts crawl and drone; merge and quicksort finish in a fraction of the steps and resolve, as the last elements slot home, into a rising pentatonic scale — the sound of order.
II · Six TemperamentsWhy quicksort usually wins
Run the race and quicksort almost always crosses the line first — yet its worst case is a disastrous n², no better than bubble sort. How does the gambler beat the guaranteed methods? C. A. R. Hoare's 1961 invention wins on the things the O-notation hides: it sorts in place with almost no extra memory, it moves along contiguous runs the cache loves, and its constant factor is tiny. Its dreaded worst case — an already-sorted input with a naïve pivot — is dodged in practice by choosing the pivot at random or from a median-of-three, making the bad case astronomically unlikely. Merge sort, by contrast, guarantees n·log·n and never betrays you, and it is stable (equal elements keep their order) — but it pays with a second array's worth of memory, which is why it rules when the data is too big for RAM and must stream from disk, the subject of the next room.
Big-O tells you how an algorithm scales; it does not tell you how it feels. Quicksort and merge sort are both n·log·n, and yet they sound, and behave, nothing alike.
Listen to the differences the counters cannot show. Insertion sort, useless on random data, becomes nearly silent and instant on a nearly-sorted array — it is adaptive, and real-world libraries switch to it for small or almost-ordered runs. Selection sort makes the fewest swaps of any method, a virtue when moving an element is expensive. Heapsort matches merge sort's guarantee in place, but scatters its reads across the array in a way the cache hates, so it sounds jagged and runs slower than its O suggests. This is the craft Knuth teaches in §5.2: there is no single best sort, only the best sort for a given machine, memory budget, and shape of data.
III · The Lower Bound as MusicOrder is a scale
There is a reason the finish of every one of these sorts sounds like a scale and not like noise. A sorted array, swept left to right, is exactly a monotonic rise in pitch — the very definition of an ascending run. The journey there is where the algorithms differ; the destination is a chord they all must strike. What you are hearing at the end is the log₂(n!) lower bound being satisfied: the moment the last inversion is undone, the last question answered, and the pile resolves from chaos into the one arrangement that lets any element be found again in an instant — which is the promise the next two rooms, on trees and on hashing, are built to keep.
"An algorithm must be seen to be believed." — D. E. Knuth
Knuth once said that of all the topics in his life's work, sorting was the one he found most purely delightful — a small, closed world where the questions are exactly stated and the answers can be proved and, as you have now heard, even sung. Change the size, change the speed, race the six temperaments against each other, and listen for the personality in each. The comparison counter is the truth an engineer must respect. The music is the truth you will remember.