Sorting
Eleven algorithms sort the same shuffle one after another, each with its own colour and sound, then race side by side: the classics, radix sort that never compares, Timsort with its runs and gallops, and bogosort, which shuffles until its timer runs out. QuickSort gets its own lab: choose the pivot, watch the recursion tree grow, ask what if, or be the pivot yourself. Turn on the stability view to see who keeps equal items in order. Pause any time to turn the bars into blocks you can throw around, then sort whatever mess you've made.
The numbers
How it works
QuickSort is divide and conquer. Pick one value, the pivot, and walk the sub-array once, moving everything smaller to its left and everything larger to its right. The pivot is now exactly where it belongs, and each side is a smaller copy of the same problem, so sort each side the same way. Every level of the recursion tree costs about n comparisons in total, so the whole job is n times the depth of the tree.
A pivot near the middle halves the work and the tree is only log₂ n deep. The smallest or largest value peels off a single item, and if that keeps happening the tree becomes a chain n deep: n²/2 comparisons. Sorted input with the first item as pivot does exactly that, which is why it is the killer input.
Random pivots make the average fast whatever the input. No arrangement of the data can predict a coin flipped at run time, so every input costs about 1.39 n log₂ n comparisons on average for large n, and a chain is astronomically unlikely. Median of three gets close to the middle without randomness, but a crafted input can still fool it.
the same few lines sort any list, and one coin flip per call turns the worst case into something you will never see.
Lomuto sweeps one pointer left to right and swaps smaller values behind a boundary; the pivot lands in its final place. Hoare walks two pointers in from both ends and swaps pairs on the wrong side; it makes about three times fewer swaps, but the pivot only ends up somewhere in its half.
Radix sort never compares two values. It deals every value into ten piles by its last digit, gathers the piles back in order, then does the same for the tens digit and the hundreds. Each pass keeps the order of the one before, so after the last digit everything is sorted: d passes of n items, with no n log n limit because nothing is ever compared.
Timsort, the sort inside Python and Java, bets that real data already has order in it. It finds runs that are already sorted (reversing ones that fall), tops short runs up with binary insertion, and merges runs whose lengths keep a balanced stack. When one run wins a merge several times in a row it gallops: it jumps ahead 1, 3, 7, 15 places to find how far that run keeps winning, then copies the whole stretch at once. Here minrun and the gallop trigger are scaled down so you can see both at 48 items.
Bogosort checks whether the list is sorted and, if not, shuffles all of it and checks again. With n different values only one of n! orders is right, so it expects n! shuffles. It gives up when its timer runs out.
Stability. A sort is stable when items that compare equal leave in the order they arrived. That matters when you sort by one thing after another: sort by name, then stably by team, and each team stays in name order. Merge, insertion, bubble, radix and Timsort are stable; selection, shell, heap, both quicksorts and bogosort can reorder equal items. Turn on the stability view and equal values share a colour, numbered by where they started.