Commissioned for this museum · after C. A. R. Hoare, 1961
Quicksort
TypeScript·1961·17 lines·430 bytes
/**
* Quicksort — choose a pivot, put the smaller things on one side and the
* larger on the other, then do the same to each side.
*/
function quicksort(xs: number[]): number[] {
if (xs.length <= 1) {
return xs;
}
const [pivot, ...rest] = xs;
return [
...quicksort(rest.filter((x) => x < pivot)),
pivot,
...quicksort(rest.filter((x) => x >= pivot)),
];
}
console.log(quicksort([5, 3, 8, 1, 9, 2, 7]).join(" "));Curator’s note
This is the beautiful quicksort, and it is not the one in your standard library. That gap is the exhibit.
What hangs here is the algorithm as an idea: partition, recurse, done, in eleven lines you can read in one breath. What ships in a real runtime is several hundred lines that sort in place, switch to insertion sort below about sixteen elements, choose the pivot from a sample rather than the first item, and fall back to heapsort when the recursion goes too deep. All of that is necessary and none of it is beautiful, and a museum is one of the few places where it is fair to show the idea without the engineering.
The version in the frame has a specific and famous flaw, put there on purpose: it takes the first element as the pivot. Hand it a list that is already sorted and every partition splits into nothing and everything, the recursion goes as deep as the list is long, and the fastest sort in common use becomes one of the slowest. Hoare's 1961 paper already suggested choosing the pivot at random. The trap is that the naive version behaves beautifully on test data and badly on real data, because real data is so often already in order.
It also allocates. Two filter calls per level means the memory used is proportional to the work done, which is the price of writing it as an expression rather than a procedure — no swapping, no indices, no mutation, and nothing you could ship. Read it the way you would read a study for a painting rather than the painting.