Tony Hoare: quicksort, the null reference, and CSP
- YT :: https://www.youtube.com/watch?v=jF3W7EkXd4k
- Original title :: He Realized his Mistake
A "programmer of the month" profile of Sir Tony Hoare — the man who invented quicksort on paper in Moscow, gave us communicating sequential processes, and also introduced the null reference in 1965, which he later called his billion-dollar mistake.
Quicksort, invented without a computer
Hoare was born in 1934 in what is now Sri Lanka, schooled in England, and entered Merton College, Oxford in 1952. National service with the Royal Navy sent him to study Russian for 18 months, and it was at Moscow State University that he worked out quicksort with pen and paper — no computer, and no programming language with recursion yet existed.
The algorithm: pick a pivot, put everything smaller on one side and everything larger on the other, then recurse into each side. Prime walks through it on an example array. Two properties made it matter: n log n runtime, and very little extra memory — which was decisive in 1960, when a kilobyte of magnetic core RAM cost $5,000, roughly $50,000 in today's money.
He got to implement it only after joining Elliott Brothers in 1960, where his first task was shell sort. He told his boss Pat he could do better, they bet sixpence, Hoare drew the algorithm on the whiteboard, Pat implemented it and conceded. Hoare also convinced Elliott Brothers to adopt ALGOL 60 rather than a bespoke proprietary language, which turned into a commercial success.
The billion-dollar mistake
Working with Niklaus Wirth on ALGOL W, Hoare designed the first comprehensive type system for references in an object-oriented language, with the goal that every reference use be provably safe. From his 2009 QCon talk: he "couldn't resist the temptation to put in a null reference, simply because it was so easy to implement", and it has since caused innumerable errors, vulnerabilities and crashes — his estimate, a billion dollars of damage.
Prime's illustration is the June 2025 Google Cloud outage: a missing null check took down the API layer and cascaded globally — roughly seven and a half hours to fully roll back, affecting Spotify among many others. He notes the counterfactual, though: if Hoare hadn't invented it, someone else would have.
Communicating sequential processes
Hoare's other landmark contribution. Prime demonstrates with Go: one goroutine creates a channel and blocks on receive, a second does work and sends. The core idea is that communication is a synchronous handshake — both sides wait for each other — and that processes are units of behaviour that don't share variables. Buffering relaxes the synchrony but not the model. If you've written Elixir, this is the actor pattern, because it is the same lineage.
Quotes and honours
On ALGOL 60: "a language so far ahead of its time that it was not only an improvement on its predecessor, but also on nearly all of its successors."
On design: "There are two ways of constructing a software design. One way is to make it so simple that there are obviously no deficiencies. The other is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult."
More than 21 honours including the Turing Award, and a knighthood for services to education and computer science. Prime also gestures at quick select, the ALGOL compiler work, the unifying theories of programming, and the dining philosophers problem. Hoare died in March of this year.