Quicksort inventor Tony Hoare reaches the base case at 92

Classicist, philosopher, wit, and one of the greatest British computer scientists of all time

Obit Professor Charles Anthony Richard Hoare has died at the age of 92. Known to many computer science students as C. A. R. Hoare, and to his friends as Tony, he was not only one of the greatest minds in the history of programming – he also came up with a number of the field's pithiest quotes.

He is best known as the inventor of the Quicksort algorithm. He invented it in 1959 and implemented it at Elliott Computers in 1960 for a bet with his boss, as recounted in this lovely personal reminiscence by Jim Miles. Depending on how ordered the data you need to sort is, an incredible two-thirds of a century later it's still one of the fastest ways to sort data.

In this interview clip, he explains how he implemented it:

Quicksort has been used in implementations of the Unix sort command and in various language libraries – but in case it helps, here's a version implemented as a Hungarian folk dance. For comparison, there are also demonstrations of other sort methods.

Quicksort (and its related Quickselect algorithm) was not Hoare's only claim to fame by far. A decade later, he devised Hoare logic, based on the Hoare triple, an important tool in reasoning about, and formally verifying, programs.

A decade on from that, he published what he called the Communicating Sequential Processes model, which now guides how programming languages including Clojure, Erlang, and Go handle concurrent operations.

He was also superbly quotable. In 1973, he said of ALGOL-60 [PDF]:

Here is a language so far ahead of its time, that it was not only an improvement on its predecessors, but also on nearly all its successors.

He won the Turing Award in 1980, and the ACM page about him has several video clips from a 2021 interview. He gave a famous lecture titled "The Emperor's Old Clothes" [PDF] in which he said:

I conclude that there are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies.

(We have recommended you read this before, and we suspect we'll do so again.)

Another of his inventions is one he deeply regretted. Along with the late Niklaus Wirth, Hoare co-designed ALGOL W, a proposed successor to ALGOL-60. Instead, the committee went with what turned into ALGOL-68, effectively ending the language. Wirth and Hoare's ALGOL W evolved into Pascal, and Hoare included a feature "simply because it was so easy to implement." It is called the Null pointer or Null reference, and Maximiliano Contieri has a rather nice illustration. Later, as in this talk from QCon in 2009, Hoare called Null references The Billion Dollar Mistake.

Born in Colombo, Sri Lanka, in 1934, he moved to Zimbabwe (then Rhodesia) during the Second World War with his mother, two younger brothers, and two younger sisters. After this, they moved to Britain, where Hoare went to Merton College at Oxford University. His later wit may owe something to his first degree, in Literae humaniores, nicknamed "Greats" [PDF] – Latin, Ancient Greek, Philosophy, and Ancient History. During his National Service, he learned Russian, and studied at Moscow State University as an exchange student. He studied machine translation with Kolmogorov, during which time he worked on the problem of sorting a list of Russian dictionary words. This gave him the idea for what later became Quicksort, implementation of which was in part enabled by ALGOL's support for recursion.

He married Jill Pym in 1962, and they had three children, Tom, Joanna, and Matthew, who died of leukaemia in 1982. Later in life, alongside being Emeritus Professor at Oxford, he worked as an emeritus researcher at Microsoft Research, which The Register mentioned in 2004.

In 2024, FACS, the Newsletter of the Formal Aspects of Computing Science, dedicated its July issue [PDF] to a tribute to Hoare for his 90th birthday. We have also seen some very good and touching posts in his memory, including "Commemorating Tony Hoare, Inventor of QuickSort," and "In Memoriam: Sir Antony Hoare (1934–2026)" by Dag Spicer at the Computer History Museum. ®