Every racer gets the same shuffled list, and each takes one comparison or one move per step. The race shows which methods do the least work.
Race bubble sort against merge sort on 20 items, then on 400. Bubble sort's work grows like n²: double the list, four times the work. Merge sort's grows like n log n, only a little over twice. Now pick Nearly sorted: insertion sort, usually a slowcoach, suddenly wins, because each item only has to slide a short way. Try Few different values with radix sort switched on. It never compares two items at all: it deals them into piles by their digits.
Then switch on Can't believe it: Stanley Fung's 2021 sort compares every item with every item and swaps whenever the first is smaller. Read it and you'd swear it sorts the wrong way round. Watch it: it doesn't. It's also the slowest racer by far, and its author asks you never to use it.
Turn on Listen and every step plays a note, pitched by the item it touched. Each method has its own sound.
John von Neumann wrote merge sort in 1945, for one of the first stored-program computers. Tony Hoare devised quicksort in 1959, while he was a visiting student in Moscow, and published it in 1961. Donald Shell published his sort in 1959, and J. W. J. Williams invented heapsort in 1964. Radix sort is older than electronic computers: Herman Hollerith's punched-card machines tabulated the 1890 US census, and the card sorters that followed dealt cards into piles one column at a time. Donald Knuth gathered the whole subject into volume 3 of The Art of Computer Programming, Sorting and Searching, in 1973.
Why does it matter? Sorting is everywhere: your contacts, search results, the leaderboards on this site. For a million items, an n² method takes about a trillion steps, nearly three hours at a hundred million steps a second. An n log n method takes about twenty million: a fifth of a second.
