Quicksort

Lore & Background

He needed to sort Russian words before looking them up in a dictionary on magnetic tape, and after finding insertion sort too slow, he devised quicksort. He wrote the partition part in Mercury Autocode but struggled with unsorted segments; upon returning to England, he was asked to write code for Shellsort, and his boss bet a sixpence that Hoare did not know a faster algorithm—a bet his boss ultimately lost.

Reader's Guide

Quicksort's significance lies in its efficiency and widespread adoption, appearing in Unix as the default library sort subroutine and lending its name to the C standard library subroutine qsort and Java's reference implementation. The algorithm is a family of closely related methods based on partitioning, with details varying across implementations. Nico Lomuto's simpler partition scheme, popularized by Bentley's Programming Pearls and Introduction to Algorithms, is easier to understand but less efficient than Hoare's original, performing three times more swaps and degrading to O(n^2) when all elements are equal.

Did You Know?

• Hoare's boss bet a sixpence that Hoare did not know a faster algorithm than Shellsort, and ultimately lost the bet.
• The algorithm is sometimes called partition-exchange sort because it partitions elements into sub-arrays based on a pivot.
• Lomuto's partition scheme, though popular in textbooks, performs three times more swaps on average than Hoare's original scheme.