About Sorting Race
Eight ways of putting a shelf of books in order by height, racing on eight copies of the same shelf. Pick the kind of shelf (RANDOM, NEARLY SORTED, REVERSED or FEW HEIGHTS) and how many books (16 to 400), then press RACE. STEP moves one tick at a time, FINISH jumps to the end, SHUFFLE deals a new shelf of the same kind. Books lit cream are being compared, red ones have just been written (put down on the shelf, or copied onto the trolley), blue ones are having a digit read. Click a method's name on the shelf list for how it works. Keys: Space race or pause, S step, F finish, N shuffle. COPY LINK copies a link to this exact shelf.
THE RULES OF THE RACE
Every shelf gets the same number of ticks. Comparing two books costs one tick; putting a book down in a place costs one tick (so swapping two books costs two); for radix sort, reading one book's digit costs one tick. Copying a book onto the spare trolley, which merge sort and radix sort need, is a write too and costs one tick, so every method pays for every book it moves. Real computers also care about memory and caches, so a race on a real machine can come out in a different order, but the counts show how each method's work grows.
THE STORY
Sorting was one of the first big jobs for machines. Punched-card sorters, from around 1900, sorted cards one column at a time: a pass for the last digit, then the next, which is radix sort. John von Neumann wrote merge sort in 1945 as one of the first programs for the EDVAC, a stored-program computer then being designed. Donald Shell published his method in 1959. Tony Hoare invented quicksort in 1959 while he was a visiting student in Moscow, and published it in 1961. J. W. J. Williams published heap sort in 1964. The name "bubble sort" was in print by the early 1960s; Donald Knuth later wrote that it "seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems".
Any method that only compares books needs, for its worst shelf of n different books, at least log₂(n!) compares, about n log₂ n: each compare is one yes-or-no answer, and it has to tell apart all n! orders the shelf could be in. Merge sort and heap sort come close; radix sort dodges the limit by never comparing at all. The sort built into Python (Timsort, by Tim Peters, 2002) mixes merge sort with insertion sort for short runs.
HOW IT WORKS
Each method sorts its own copy of the shelf as soon as the shelf is dealt, writing down every compare, write and read. The race plays those lists back, the same number of ticks for every shelf each moment, so the finishing order is just the total ticks. The counts on the shelf list match what the methods really did (the test file checks them against the known sums: bubble sort on a reversed shelf of 100 makes 4,950 compares and 4,950 swaps). Quicksort here uses Hoare's own way of splitting, with the middle book as the pivot; Shell sort uses Marcin Ciura's gaps (1, 4, 10, 23, 57, 132, 301) from 2001; radix sort works in base 10, units first.
FURTHER WATCHING AND READING