Quicksort
Efficient divide-and-conquer sorting algorithm developed by Tony Hoare.
Quicksort is a widely used, efficient sorting algorithm that works well for general purposes. It was created by British computer scientist Tony Hoare in 1959, with a publication following in 1961. The algorithm follows a divide-and-conquer approach: it picks a "pivot" element from the array and then splits the remaining elements into two groups—those smaller than the pivot and those larger than it. This process is why it's also called partition-exchange sort. These sub-arrays are then sorted recursively. For randomized data, especially on larger sets, quicksort tends to be a bit faster than merge sort or heapsort. It is a comparison sort, meaning it works with any data type that has a defined "less-than" relationship (a total order). However, most quicksort implementations are not stable, so the original order of equal items is not kept.
Hoare developed quicksort in 1959 while a visiting student at Moscow State University, working on a machine translation project for the National Physical Laboratory. He needed to sort Russian words for dictionary lookup on magnetic tape, and after finding insertion sort too slow, he devised the new algorithm. He wrote the partition routine in Mercury Autocode but struggled with managing unsorted segments. Returning to England, he was asked to code Shellsort, but told his boss he knew a faster method; his boss bet him a sixpence he did not, a bet the boss ultimately lost. Hoare published the algorithm with theoretical analysis in *The Computer Journal* in 1962. Later, after learning ALGOL’s recursion capabilities, he published an improved version in the *Communications of the ACM* in 1961. Quicksort became widely adopted, appearing in Unix as the default sort subroutine and lending its name to the C standard library function `qsort` and Java’s reference implementation. Robert Sedgewick’s 1975 PhD thesis resolved many open problems regarding pivot selection schemes. In 1993, Jon Bentley and Doug McIlroy added improvements for libraries, including handling equal elements and a “pseudomedian of nine” pivot scheme. Bentley later popularized a simpler partition scheme by Nico Lomuto, though it performs more swaps and degrades to quadratic runtime when all elements are equal. McIlroy produced an “AntiQuicksort” function in 1998 that forces even the 1993 variant into quadratic behavior by generating adversarial data.
- developed_by
- Tony Hoare
- type
- Divide-and-conquer sorting algorithm
- average_complexity
- O(n log n)
- worst_case_complexity
- O(n^2)
- also_known_as
- Partition-exchange sort
Verified Timeline
Lore & Background
The quicksort algorithm was developed in 1959 by Tony Hoare while he was a visiting student at Moscow State University. At that time, Hoare was working on a machine translation project for the National Physical Laboratory. As a part of the translation process, he needed to sort the words in Russian sentences before looking them up in a Russian-English dictionary, which was in alphabetical order on magnetic tape. After recognizing that his first idea, insertion sort, would be slow, he came up with a new idea. He wrote the partition part in Mercury Autocode but had trouble dealing with the list of unsorted segments. On return to England, he was asked to write code for Shellsort. Hoare mentioned to his boss that he knew of a faster algorithm, and his boss bet a sixpence that he did not. His boss ultimately accepted that he had lost the bet. Hoare published a paper about his algorithm, including a theoretical analysis, in The Computer Journal Volume 5, Issue 1, 1962, Pages 10–16. Later, Hoare learned about ALGOL and its ability to do recursion, which enabled him to publish an improved version of the algorithm in ALGOL in Communications of the Association for Computing Machinery. The ALGOL code is published in Communications of the ACM (CACM), Volume 4, Issue 7 July 1961, pp 321 Algorithm 63: partition and Algorithm 64: Quicksort.
Reader's Guide
Quicksort gained widespread adoption, appearing, for example, in Unix as the default library sort subroutine. Hence, it lent its name to the C standard library subroutine qsort and in the reference implementation of Java. Robert Sedgewick's PhD thesis in 1975 is considered a milestone in the study of Quicksort where he resolved many open problems related to the analysis of various pivot selection schemes including Samplesort, adaptive partitioning by Van Emden as well as derivation of expected number of comparisons and swaps. Jon Bentley and Doug McIlroy in 1993 incorporated various improvements for use in programming libraries, including a technique to deal with equal elements and a pivot scheme known as pseudomedian of nine, where a sample of nine elements is divided into groups of three and then the median of the three medians from three groups is chosen. Bentley described another simpler and compact partitioning scheme in his book Programming Pearls that he attributed to Nico Lomuto. Later Bentley wrote that he used Hoare's version for years but never really understood it but Lomuto's version was simple enough to prove correct. Bentley described Quicksort as the "most beautiful code I had ever written" in the same essay. Lomuto's partition scheme was also popularized by the textbook Introduction to Algorithms although it is inferior to Hoare's scheme because it does three times more swaps on average and degrades to O(n^2) runtime when all elements are equal. McIlroy would further produce an AntiQuicksort (aqsort) function in 1998, which consistently drives even his 1993 variant of Quicksort into quadratic behavior by producing adversarial data on-the-fly.
Did You Know?
- Quicksort was developed in 1959 by Tony Hoare while he was a visiting student at Moscow State University, working on a machine translation project for the National Physical Laboratory.
- Hoare's boss bet a sixpence that Hoare did not know a faster algorithm than Shellsort; his boss ultimately accepted that he had lost the bet.
- The ALGOL code for quicksort was published in Communications of the ACM, Volume 4, Issue 7 July 1961, pp 321 as Algorithm 63: partition and Algorithm 64: Quicksort.
- Robert Sedgewick's PhD thesis in 1975 resolved many open problems related to the analysis of various pivot selection schemes for quicksort.
- McIlroy produced an AntiQuicksort (aqsort) function in 1998 that consistently drives even his 1993 variant of quicksort into quadratic behavior by producing adversarial data on-the-fly.
More in Algorithms And Data Structures 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