“Quicksort Inventor Tony Hoare dies”

I found out late last week that one of the heroes of early computing passed away on March 5, 2026, at the age of 92. Professor Charles Anthony Richard Hoare was more commonly known as C. A. R. Hoare by his students and Tony by his friends. Hoare is considered one of the greatest minds in the history of programming. He is best known for his invention of the Quicksort algorithm. This is the industry standard algorithm when it comes to sorting data; even today with our much more efficient computing systems, no one has found a faster way to sort information.

He invented the algorithm in 1959, and implemented it at Elliot Computers in 1960 as part of a bet with his boss, Jim Miles. Even more than 75 years later, it is still among the fastest ways to sort data. Quicksort was only one of his many claims to fame. A decade later he devised Hoare logic, where he defined sections of a program with what he labeled a Hoare Triple, looking at the preconditions (P), the command (C) and the Postcondition (Q). This allowed people to rapidly verify the functionality of code without having to use the prior method of manually creating graphical flowcharts to evaluate code. His methods vastly improved software verification and is still among the leading methods used today.

In 1980 Hoare won the prestigious Turning Award, which is given to leaders in the computing community by the Association of Computing Machinery (ACM). This reward was the result of his years of algorithm design and improvements. His research into improving the speed of such things as sort, search, and categorizing data, as well as contributions to code verification and validation has named him as one of the few nominated for the Turning Award. Hoare is one of my all-time heroes of computing.

Let me give you a quick overview of his most well-known algorithm, the Quicksort, how it works, and why it is faster than other sorting mechanisms. You can try his algorithm yourself by pulling out a deck of cards and grabbing all the cards from a single suit. Don’t sort them, just pull them out, leaving them in random order. Now we choose a single card to be what the algorithm calls the pivot card. It can be any random card from the pile. We usually just choose the top card of the stack.

Next, we sort the remaining cards into two piles, one for cards higher than the pivot and one for cards lower than the pivot card value. Note we are not sorting these piles, just separating them. Then we place the pivot card between the two piles; it is now in its final position in the sort. We know it belongs here because everything in the below pile is lower and everything in the above pile is higher. Now we just repeat this process for each new pile of cards until each pile only has one card and then we can simply pick the cards up in order.

I know initially it seems like this would be very slow because we are looking at each card every time we split the pile, which means in our worst case we compare the cards n*n times, which turns out being exactly the same as insertion sort. This is the way we usually sort cards ourselves—insertion sort, which means we just place cards in order based on which two cards it fits between and we place them one at a time. However, the more random the cards are, the less likely the worst case occurs in quicksort, and for insertion sort you always do n*n comparisons. It’s not the worst case, it is the only case, which is what makes quicksort faster. I suggest doing this as a challenge with a friend, one of you use quicksort and the other insertion sort and see who sorts their stack of cards faster.

I have tried sorting cards this way and it is much faster when sorting things like a stack of counting cards between one and 100, but seems slower for smaller sets of cards, like a single suit of a card deck, thirteen cards, but we need to realize that computers can only compare two values at a time and our minds can do multiple comparisons, which makes us much faster at sorting cards. If we add a rule to our sort challenge that we can only look at two cards at a time, quicksort suddenly becomes much faster than any other method.

Until next week, stay safe and learn something new.

Scott Hamilton is an Expert in Emerging Technologies at ATOS and can be reached with questions and comments via email to shamilton@techshepherd.org or through his website at https://www.techshepherd.org.