On this page
Sorting is one of the first algorithms every computer science student learns, usually starting with bubble sort. It works, but it slows down badly as lists grow. Quicksort is the method that showed how much faster sorting could be, and it came from a philosophy graduate trying to look up words for machine translation. This post covers Tony Hoare's story, a worked example of quicksort, its speed compared with bubble sort, the common mistakes and what students can learn from him.
Who was Tony Hoare?
The ACM Turing Award page for Hoare records that Charles Antony Richard Hoare was born on 11 January 1934 in Colombo, in what is now Sri Lanka. At Oxford he studied "Greats": Latin, Greek and philosophy. After national service in the Royal Navy he returned to Oxford to study statistics and learned to program. The University of Oxford's Department of Computer Science gives the date of his death as 5 March 2026.
How did Hoare discover quicksort?
In 1959 Hoare went to Moscow State University as a graduate student to work on machine translation of languages. The Oxford page says that "to assist in efficient look-up of words in a dictionary, he discovered the well-known sorting algorithm Quicksort." The ACM page adds that he saw sorting as an important problem there and first thought of the method in Moscow.
Back in England in 1960 he joined Elliott Brothers, a small computer maker, and led the team that built a compiler for the language ALGOL 60. During a course on ALGOL 60, the ACM page notes, he saw that recursion was the key to expressing quicksort clearly. He published it as "Algorithm 64: Quicksort" in Communications of the ACM in 1961 and as a full paper, "Quicksort", in The Computer Journal in 1962.
Worked example: sorting six numbers with quicksort
Sort [6, 3, 8, 1, 9, 2]. This version is simplified for clarity. Hoare's original swaps items in place instead of building new lists, but the idea is the same.
Pick a pivot. Take the first item, 6.
Split. Smaller than 6: [3, 1, 2]. Larger: [8, 9].
Sort [3, 1, 2]. Pivot 3. Smaller: [1, 2]. Larger: none.
Sort [1, 2]. Pivot 1. Smaller: none. Larger: [2], a single item, already sorted. Result: [1, 2].
So [3, 1, 2] becomes [1, 2] + [3] = [1, 2, 3].
Sort [8, 9]. Pivot 8. Larger: [9]. Result: [8, 9].
Join: [1, 2, 3] + [6] + [8, 9] = [1, 2, 3, 6, 8, 9].
In Python:
def quicksort(items):
if len(items) <= 1:
return items
pivot = items[0]
smaller = [x for x in items[1:] if x < pivot]
larger = [x for x in items[1:] if x >= pivot]
return quicksort(smaller) + [pivot] + quicksort(larger)
print(quicksort([6, 3, 8, 1, 9, 2])) # [1, 2, 3, 6, 8, 9]How much faster is quicksort than bubble sort?
Bubble sort compares neighbouring pairs. In its basic form it makes (n − 1) + (n − 2) + ... + 1 = n(n − 1)/2 comparisons. For 1,000 items that is 1,000 × 999 ÷ 2 = 499,500 comparisons.
When quicksort's pivots split lists fairly evenly, each level of splitting does about n comparisons, and halving 1,000 items down to single items takes about log₂ 1,000 ≈ 10 levels. That is roughly 1,000 × 10 = 10,000 comparisons, as a rough estimate, about 50 times fewer.
There is a catch. If the list is already sorted and you always pick the first item as pivot, every split leaves one side empty. Then quicksort also needs about n(n − 1)/2 comparisons. Programmers avoid this by choosing the pivot more carefully, for example at random.
Our guide to searching and sorting in Python covers bubble sort and binary search step by step for comparison.
What mistakes do students make with quicksort?
No base case. Without "if len(items) <= 1: return items", the function calls itself forever.
Losing duplicates. If you keep only x < pivot and x > pivot, equal values vanish. Put them on one side, as with >= above.
Including the pivot in a sublist. Splitting items, not items[1:], puts the pivot back in and can recurse forever.
Assuming it is always fast. A sorted list with a first-item pivot is the slow case.
What else did Hoare contribute?
The Oxford department's tribute lists Hoare logic, proposed in 1969 as a way to prove programs correct, and Communicating Sequential Processes, a mathematical model of programs that run at the same time. He received the 1980 ACM Turing Award "for his fundamental contributions to the definition and design of programming languages" and was knighted in 2000.
What can a student take from how Hoare worked?
Start from a real need. Quicksort came from looking up words for translation.
Find the right way to express an idea. Recursion made quicksort easy to state.
Learn from failure. The ACM page says a failed operating system project at Elliott shaped his later work on programs running at the same time.
Prove, don't just test. His later work was about showing programs are correct.
When a recursive function will not behave, the Fermi Problem Library has worked problems with a step-by-step solver that explains the reasoning rather than printing an answer.
Try it now: sort [5, 5, 2, 7, 1] by hand with the method above, then run the code to check you get [1, 2, 5, 5, 7].
