Turing Award winner Tony Hoare, computing pioneer who invented the Quicksort algorithm for a sixpence bet, dies at the age of 92

Professor Charles Anthony Richard Hoare, known as Tony to friends, has died at the age of 92. One of the greatest programmers in the early history of computing, he invented the Quicksort algorithm after a bet with his boss, later devised Hoare logic (a system for rigorously assessing the correctness of a program), and was the co-designer of ALGOL W, a programming language that would become the basis for Pascal.

Hoare was also a deeply funny, philosophical, and self-deprecating man who had a hundred other achievements to his name. On winning the Turing Award in 1980, he delivered a lecture called The Emperor’s Old Clothes in which he gave a wry look back at his career’s successes and failures, and used them to bemoan overly complex software and bloated systems, urging programmers to focus on simplicity and security instead.

“You know, you shouldn’t trust us intelligent programmers,” said Hoare in the lecture. “We can think up such good arguments for convincing ourselves and each other of the utterly absurd. Especially don’t believe us when we promise to repeat an earlier success, only bigger and better next time.”

Hoare invented the Quicksort algorithm at Elliott Computers after a wager with his boss in 1959. Remarkably, it remains one of the fastest ways to sort particular datasets. Here is the story of its creation, as recounted by his friend Jim Miles.

“A story that I was determined to hear from the source was the legendary Quicksort ‘wager'” says Miles of one of his last visits with Hoare. “The story goes that Tony told his boss at Elliott Brothers Ltd that he knew a faster sorting algorithm than the one that he had just implemented for the company. He was told ‘I bet you sixpence you don’t!’. Lo and behold, Quicksort WAS faster.

“One detail I might be able to add is that I asked Tony if indeed the wager was paid out or if it had merely been a figure of speech. He confirmed that indeed he WAS paid the wager! A detail of this story that I find particularly reflective of Tony’s humble personality is that he went ahead and implemented the slower algorithm he was asked to, while he believed Quicksort to be faster, and before chiming in with this belief. It speaks to a professionalism that Tony always carried.”

Among Hoare’s other achievements was the Communicating Sequential Processes model, which has since evolved considerably and remains the subject of active research: this is a formal language for describing patterns of interaction in concurrent systems, which guides programming languages including Clojure, Erlang, and Go in how they handle concurrent operations.

He is also responsible for many almost Wildean aphorisms about his work, and that of others. In 1973 he said of ALGOL-60: “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.”

Perhaps Hoare’s most oft-quoted line comes from the above-mentioned Turing lecture (thanks, The Register):

“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.”

Hoare was born in Colombo, Sri Lanka, in 1934. During World War 2 the family moved to Zimbabwe, known then as Rhodesia, and then to Britain, where Hoare would go on to study Literae humaniores (Classics) at Merton College, Oxford. Hoare served in the Royal navy, where he learned Russian and studied at Moscow University, and worked with the great Soviet mathematician Andrey Kolmogorov: a problem-solving exercise involving Russian words would give him the idea for what later became Quicksort.

He married Jill Pym in 1962, and they had three children. As well as the Turing Award in 1980, Hoare’s incredible list of honours includes the Harry H. Goode Memorial Award (1981), the Faraday Medal (1985), the Computer Pioneer Award (1990), the Kyoto Prize (2000), the IEEE John von Neumann Medal (2011), and the Royal Medal (2023). In 2000 he was Knighted by Queen Elizabeth II for services to education and computer science.