How a bet over a sorting algorithm changed computer science forever

How a bet over a sorting algorithm changed computer science forever
Image: Intellect (generated)

In short: In 1959, Tony Hoare developed Quicksort to solve a machine translation problem. When his boss doubted its efficiency, a sixpence bet was placed—and lost. Today, this divide-and-conquer algorithm remains a cornerstone of computing, proving that elegant, recursive logic can outperform more intuitive methods on large, randomized datasets.

Quicksort operates by selecting a pivot element and partitioning an array into two sub-arrays: one containing elements smaller than the pivot, and another containing elements larger. This recursive process continues until the entire array is sorted. Because it works in-place, it requires minimal additional memory, making it a highly efficient, general-purpose tool. Unlike some other sorting methods, Quicksort is not stable, meaning the relative order of equal items is not guaranteed to be preserved.

The algorithm's performance is heavily dependent on how the pivot is chosen. Tony Hoare’s original scheme, which uses two pointers moving toward each other, is generally more efficient than the popular Lomuto partition scheme, which uses a single index. Lomuto’s version is often taught in textbooks because it is easier to implement, but it performs three times more swaps on average and can degrade to quadratic time complexity if the input is already sorted. Hoare’s version, when implemented with a middle-element pivot, avoids these pitfalls and maintains optimal performance.

The evolution of Quicksort reflects the iterative nature of computer science. Researchers like Robert Sedgewick, Jon Bentley, and Doug McIlroy have spent decades refining pivot selection and partitioning to handle edge cases, such as arrays with many identical elements. Even with these advancements, the algorithm remains a target for optimization and study. Its history—from a student's project at Moscow State University to a standard library staple in Unix and Java—highlights how a simple, recursive idea can become a foundational pillar of modern software engineering.

Opens the Intellect+ feed with this card first. Swipe up for the next one.

Sources

To cite this card, link to https://intellectplus.co.uk/app/science-quicksort.

How we source, check and correct cards: Editorial standards.

General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.

Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?

Related

Finding something worth knowing…