Quicksort inventor Tony Hoare reaches the base case at 92
- Reference: 1773325435
- News link: https://www.theregister.co.uk/2026/03/12/in_memoriam_sir_tony_hoare/
- Source link:
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 [1]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 [2]fastest ways to sort data .
In this interview clip, he explains how he implemented it:
[3]
[4]Youtube Video
[5]
[6]
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 [7]implemented as a Hungarian folk dance . For comparison, there are also [8]demonstrations of other sort methods .
[9]Youtube Video
[10]
Quicksort (and its related [11]Quickselect algorithm ) was not Hoare's only claim to fame by far. A decade later, he devised [12]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 [13]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 [14]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 [15]ACM page about him has several video clips from a 2021 interview. He gave a famous lecture titled " [16]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 [17]recommended you read this before , and we suspect we'll do so again.)
[18]RIP: Bill Atkinson, co-creator of Apple Lisa and Mac
[19]One of the last of Bletchley Park's quiet heroes, Betty Webb, dies at 101
[20]RIP Raymond Bird: Designer of UK's first mass-produced business computer dies aged 101
[21]BASIC co-creator Thomas Kurtz hits END at 96
Another of his inventions is one he deeply regretted. Along with the [22]late Niklaus Wirth , Hoare co-designed ALGOL W, a [23]proposed successor to ALGOL-60 . Instead, the committee went with [24]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 [25]Null pointer or Null reference, and [26]Maximiliano Contieri has a rather nice illustration . Later, as in this talk from QCon in 2009, Hoare called Null references [27]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 , [28]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 [29]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.
[30]
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 [31]Emeritus Professor at Oxford , he worked as an emeritus researcher at Microsoft Research, which The Register [32]mentioned in 2004 .
In 2024, FACS, the Newsletter of the Formal Aspects of Computing Science, dedicated its [33]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 " [34]Commemorating Tony Hoare, Inventor of QuickSort ," and " [35]In Memoriam: Sir Antony Hoare (1934–2026) " by Dag Spicer at the Computer History Museum. ®
Get our [36]Tech Resources
[1] https://blog.computationalcomplexity.org/2026/03/tony-hoare-1934-2026.html
[2] https://builtin.com/machine-learning/fastest-sorting-algorithm
[3] https://pubads.g.doubleclick.net/gampad/jump?co=1&iu=/6978/reg_software/front&sz=300x50%7C300x100%7C300x250%7C300x251%7C300x252%7C300x600%7C300x601&tile=2&c=2abLxOEBmMQubL1szYEzz1wAAAcg&t=ct%3Dns%26unitnum%3D2%26raptor%3Dcondor%26pos%3Dtop%26test%3D0
[4] https://www.youtube.com/watch?v=pJgKYn0lcno
[5] https://pubads.g.doubleclick.net/gampad/jump?co=1&iu=/6978/reg_software/front&sz=300x50%7C300x100%7C300x250%7C300x251%7C300x252%7C300x600%7C300x601&tile=4&c=44abLxOEBmMQubL1szYEzz1wAAAcg&t=ct%3Dns%26unitnum%3D4%26raptor%3Dfalcon%26pos%3Dmid%26test%3D0
[6] https://pubads.g.doubleclick.net/gampad/jump?co=1&iu=/6978/reg_software/front&sz=300x50%7C300x100%7C300x250%7C300x251%7C300x252%7C300x600%7C300x601&tile=3&c=33abLxOEBmMQubL1szYEzz1wAAAcg&t=ct%3Dns%26unitnum%3D3%26raptor%3Deagle%26pos%3Dmid%26test%3D0
[7] https://www.i-programmer.info/news/150-training-a-education/2379-at-last-quicksort-the-dance.html
[8] https://www.i-programmer.info/news/150-training-a-education/2255-sorting-algorithms-as-dances.html
[9] https://www.youtube.com/watch?v=ywWBy6J5gz8
[10] https://pubads.g.doubleclick.net/gampad/jump?co=1&iu=/6978/reg_software/front&sz=300x50%7C300x100%7C300x250%7C300x251%7C300x252%7C300x600%7C300x601&tile=4&c=44abLxOEBmMQubL1szYEzz1wAAAcg&t=ct%3Dns%26unitnum%3D4%26raptor%3Dfalcon%26pos%3Dmid%26test%3D0
[11] https://www.geeksforgeeks.org/dsa/quickselect-algorithm/
[12] https://cs.stanford.edu/people/eroberts/courses/soco/projects/2008-09/tony-hoare/logic.html
[13] https://dl.acm.org/doi/10.1145/359576.359585
[14] https://web.eecs.umich.edu/~bchandra/courses/papers/Hoare_Hints.pdf#page=28
[15] https://amturing.acm.org/award_winners/hoare_4622167.cfm
[16] https://noncombatant.org/hoare-emperors-old-clothes-turing-award/hoare-emperors-old-clothes.pdf
[17] https://www.theregister.com/2025/08/30/programmers_watch_your_weight/
[18] https://www.theregister.com/2025/06/11/bill_atkinson_obituary/
[19] https://www.theregister.com/2025/04/02/bletchley_webb_obituary/
[20] https://www.theregister.com/2025/02/11/hollerith_electronic_computer_designer_raymond_bird/
[21] https://www.theregister.com/2024/11/20/rip_thomas_kurtz/
[22] https://www.theregister.com/2024/01/04/niklaus_wirth_obituary/
[23] https://www.theregister.com/2020/05/15/algol_60_at_60/
[24] https://www.theregister.com/2025/01/07/algol_68_comes_to_gcc/
[25] https://maximilianocontieri.com/null-the-billion-dollar-mistake#heading-the-excuse
[26] https://maximilianocontieri.com/null-the-billion-dollar-mistake#heading-the-excuse
[27] https://www.infoq.com/presentations/Null-References-The-Billion-Dollar-Mistake-Tony-Hoare/
[28] https://www.classics.ox.ac.uk/sitefiles/greats-handbook-2026-.pdf
[29] https://mathshistory.st-andrews.ac.uk/Biographies/Kolmogorov/
[30] https://pubads.g.doubleclick.net/gampad/jump?co=1&iu=/6978/reg_software/front&sz=300x50%7C300x100%7C300x250%7C300x251%7C300x252%7C300x600%7C300x601&tile=3&c=33abLxOEBmMQubL1szYEzz1wAAAcg&t=ct%3Dns%26unitnum%3D3%26raptor%3Deagle%26pos%3Dmid%26test%3D0
[31] https://www.cs.ox.ac.uk/people/tony.hoare/
[32] https://www.theregister.com/2004/06/14/grand_challenge_compsci/
[33] https://www.bcs.org/media/1wrosrpv/facs-jul24.pdf
[34] https://www.i-programmer.info/news/82-heritage/18718-commemorating-tony-hoare-inventor-of-quicksort.html
[35] https://computerhistory.org/blog/in-memoriam-sir-antony-hoare-1934-2026/
[36] https://whitepapers.theregister.com/
I have been thinking the same sort of thing ... no pun intended !!!
All the names in all the fields that I considered 'important' are shuffling off this mortal coil.
Plus lots of people from the Culture section of the Sunday Magazine ... so to speak !!!
Damn ,,, the grim reaper is getting closer to me all the time !!!
:)
I've noticed the same with musical icons. All my faves are now getting old. Eric Clapton is in his 80s, Mark Knopfler in his mid 70s. We just lost Chris Rea last year.
We need a poignancy icon! Stop icon selected in honour of Mr. Hoare reaching his STOP instruction at the ripe old age of 92. Rest easy.
Jello Biafra just had a stroke a few days ago. Best wishes on his recovery..
Shouldn't that be a RETURN instruction?
I had a final year module mid 80's on formal methods the textbook for which was CSP. The book is still on my bookshelf, probably in close to pristine condition, it didn't see a lot of action then and none since. That module was hard work. All I remember is it heavily featured the dining philosophers problem which we may or may not have proved a solution to...
Didn't realise he also had a hand in Pascal. That was the teaching language at uni and knowledge of it helped me get a couple of commercial gigs, one nearly 20 years later! I've probably relied on quicksort (or a close relative thereof) via std::sort on more than a few occasions. Thank you Tony!
I had a sort-of premonition/pondering just last week that we must be getting to the time when a lot of these giants from the first generation of wide-spread computer science are going to be leaving us. Some have already gone of course, but we're facing the reality of a really important part of living-memory becoming pure history and that's a sad moment for the 'youngest science'. When I studied in the late 90s Hoare was in his 60s, and like all the textbook-name language & algorithm pioneers, still going strong. Aside from a very few early theoretical proto-computer scientists (Turing etc) we took it for granted that the field was composed of living people you could often just email there and then, if you had the guts.
I use Quicksort daily (and I genuinely smile when I get to use Quickselect because it's one of those algorithms that feels a bit magic), but I'll most remember him for his Billion Dollar Mistake talk because he eloquently and humbly leveraged his gravitas to shine a light on a very contemporaneous problem in a way that was accessible and thought-provoking. That people are still debating the value of that 17 years on is testament to how confident he was in the relevance of his decades of wisdom, even in his later years. Hope for us all. Don't get stuck in your ways, stay young, question your choices as the evidence rolls in.
RIP Tony.
:=)
Love the Quicksort as a Hungarian folk dance ... so clever and funny !!!
(See the links to other videos at the end of the clip)
Roughly equates to the 'AI' version ... looks good, very plausible as an answer BUT there is no indication that there might be a better way of implementing it !!!
:)
Re: :=)
I enjoyed that too.
Re: :=)
A true implementation using Hungarian notation... :)
For several years he was also prof. at Queens, Belfast.
In a data structures course for an exam we were required to pseudo-code various sorts, quick sort was one of the methods on the exam. Several of us studied together and had a rhyme for both quicksort and heapsort that I can't remember anymore.
In another course "communicating sequential processes" was required reading referred to in a compiler construction course also.
Thank you Prof. Hoare and Godspeed on your continuing journey.
"Null reference == $B mistake"
I have always viewed this as a joke -- a reference has to have some value, and any default can cause problems.
I must be getting old - all of the greats I studies when I was at university back in the 1980's are finally hitting their STOP instruction.
RIP Prof. C. A. R. Hoare.