Quicksort
Efficient divide-and-conquer sorting algorithm developed by Tony Hoare.
Quicksort is a highly efficient, general-purpose sorting algorithm that operates on the divide-and-conquer principle. It works by selecting a single element, called the pivot, and then rearranging the other elements into two groups: those less than the pivot and those greater than it. This process, known as partitioning, is why the algorithm is sometimes called partition-exchange sort. The two resulting sub-arrays are then sorted recursively using the same method. A key advantage is that this entire process can be performed in-place, requiring only a small, fixed amount of additional memory. As a comparison sort, it relies solely on a "less-than" relation to order items, meaning it can sort any data type that has a defined total order. However, most implementations are not stable, so the original relative order of equal elements is not guaranteed to be preserved.
On average, quicksort requires O(n log n) comparisons to sort n items, making it slightly faster than both merge sort and heapsort for randomized data, especially on larger datasets. In its worst-case scenario, however, it makes O(n²) comparisons. The algorithm was developed in 1959 by British computer scientist Tony Hoare while he was a visiting student at Moscow State University, working on a machine translation project. He needed to sort Russian words for dictionary lookups and, finding insertion sort too slow, devised the quicksort method. After returning to England, Hoare published the algorithm in 1961, and later refined it using the recursive capabilities of the ALGOL programming language. Quicksort became widely adopted, appearing as the default sorting subroutine in Unix and lending its name to the `qsort` function in the C standard library, as well as being used in the reference implementation of Java. Significant milestones in its study include Robert Sedgewick's 1975 PhD thesis, which resolved many open problems, and later improvements by Jon Bentley and Doug McIlroy, who incorporated techniques for handling equal elements and a pivot selection scheme called pseudomedian of nine.
- developed_by
- Tony Hoare
- field
- Computer science
- nationality
- British
- known_for
- Quicksort algorithm
Lore & Background
Quicksort is a highly efficient, general-purpose sorting algorithm that operates on the divide-and-conquer principle. It selects a pivot element from the array and partitions the remaining elements into two sub-arrays: those less than the pivot and those greater than the pivot, a process that gives it the alternative name partition-exchange sort. The sub-arrays are then sorted recursively, and the algorithm can be performed in-place with minimal additional memory. As a comparison sort, it works on any data type with a defined total order, but most implementations are not stable, meaning equal items may not retain their original relative order. On average, quicksort makes a specific number of comparisons to sort n items, though its worst-case performance requires a different number of comparisons. The algorithm was created in 1959 by British computer scientist Tony Hoare while he was a visiting student at Moscow State University, working on a machine translation project that required sorting Russian words before looking them up in an alphabetized dictionary on magnetic tape. After finding insertion sort too slow, he devised quicksort, writing the partition routine in Mercury Autocode. Upon returning to England, his boss bet a sixpence that Hoare did not know a faster algorithm than Shellsort—a bet the boss ultimately lost. Hoare published the algorithm in 1962 in *The Computer Journal*, later improving it using recursion in ALGOL. Quicksort became widely adopted, appearing as the default sort in Unix, the C standard library subroutine qsort, and the reference implementation of Java. Robert Sedgewick’s 1975 PhD thesis resolved many open problems in quicksort analysis, while Jon Bentley and Doug McIlroy’s 1993 version incorporated improvements for handling equal elements and a pivot scheme called pseudomedian of nine. Bentley also popularized a simpler partitioning scheme by Nico Lomuto, though it performs more swaps on average and degrades to quadratic runtime when all elements are equal.
Reader's Guide
Quicksort's significance lies in its efficiency and widespread adoption. It is a divide-and-conquer algorithm that, on average, takes O(n log n) comparisons to sort n items, though in the worst case it makes O(n²) comparisons. The algorithm gained widespread use, appearing in Unix as the default library sort subroutine and lending its name to the C standard library subroutine qsort and the reference implementation of Java. Nico Lomuto's partition scheme, popularized by Bentley's book Programming Pearls and the textbook Introduction to Algorithms, is simpler but less efficient than Hoare's original scheme, doing three times more swaps on average and degrading to O(n²) when all elements are equal.
Did You Know?
- Hoare's boss bet a sixpence that Hoare did not know a faster algorithm than Shellsort, a bet the boss lost.
- The algorithm appears in Unix as the default library sort subroutine and lent its name to the C standard library subroutine qsort.
- Lomuto's partition scheme, though simpler, does three times more swaps on average than Hoare's scheme.
Frequently Asked Questions
What is Quicksort's core role in the sorting landscape?
Quicksort is a divide-and-conquer comparison sort that works by choosing a pivot element and recursively partitioning the remaining items into two sub-arrays around that pivot. It is one of the most commonly deployed general-purpose sorting algorithms in practice.
How does Quicksort stack up against merge sort and heapsort?
On typical randomized input, Quicksort tends to outperform both merge sort and heapsort by a small margin. It also has the practical advantage of being implementable in-place, so it does not demand large auxiliary memory.
Why is Quicksort still considered important in computer science?
Even more than sixty years after its publication, Quicksort remains a go-to choice for in-memory sorting because of its speed, in-place operation, and clean recursive structure. It also serves as a canonical teaching example for the divide-and-conquer paradigm in complexity theory.
More in Complexity Theory 1-24
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record