Quicksort
This page gives a brief introduction to quicksort.
Definition
Quicksort, also known as partition-exchange sort, is a widely used sorting algorithm.
Basic principle and implementation
Procedure
Quicksort sorts an array by divide and conquer.
It has three steps:
- Partition the sequence into two parts (subject to a condition on how their values compare);
- Recurse into the two subsequences and quicksort each of them;
- Skip the combine step: there is nothing to do, because the sequence is now fully sorted.
Unlike merge sort, the first step does not simply cut the sequence into a front part and a back part: the partition must keep the two parts in order relative to each other. Specifically, it divides the sequence into two parts so that no number in the first subsequence is greater than any number in the second. To guarantee the average-case time complexity, a number \(m\) is usually chosen at random as the boundary between the two subsequences.
Then maintain two pointers, a front pointer \(p\) and a back pointer \(q\), and check each number in turn to see whether it is on the side where it belongs (front or back). If it is not, for example if the back pointer \(q\) meets a number smaller than \(m\), swap the numbers at positions \(p\) and \(q\) and advance \(p\) by one position. Once the current number is in the right place, move the pointers and carry on until they meet.
In fact, quicksort does not prescribe how to carry out the first step: both choosing \(m\) and partitioning can be done in more than one way.
In the third step, each of the two sequences is already sorted and no number in the first is greater than any number in the second, so concatenating them is all that is left.
The basic implementations below choose the pivot at a fixed position: the non-recursive C++ implementation takes the last element of the current subarray, and the recursive C++ implementation and the Python implementation take the first. They do not randomize the choice of pivot, and can degrade to \(O(n^2)\) on inputs such as sorted ones.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | |
Properties
Stability
Quicksort is an unstable sorting algorithm.
Time complexity
The best-case time complexity and the average-case time complexity of quicksort are \(O(n\log n)\), and its worst-case time complexity is \(O(n^2)\).
In the best case, every pivot chosen is the median of its sequence. The running time then satisfies the recurrence \(T(n) = 2T(\dfrac{n}{2}) + \Theta(n)\), and by the master theorem, \(T(n) = \Theta(n\log n)\).
In the worst case, every pivot chosen is the minimum or the maximum of its sequence. The running time then satisfies the recurrence \(T(n) = T(n - 1) + \Theta(n)\), which sums to \(T(n) = \Theta(n^2)\).
The expected-time analysis below assumes that the keys are distinct and that each pivot is chosen uniformly at random from the current subarray.
Proof
We now prove that in this case the algorithm runs in \(O(n\log n)\).
Lemma 1: Suppose that quicksort on an array of \(n\) elements compares \(X\) distinct pairs of elements while partitioning. Then it runs in \(O(n + X)\).
Every partition picks one element as the pivot, so at most \(n\) partitions take place. During partitioning each pair of elements is compared only a constant number of times, and the work spent on comparisons is of the same order as the number of other basic operations, so the total running time is \(O(n + X)\).
Let \(a_i\) be the \(i\)-th smallest number of the original array, and define \(A_{i,j}\) as \(\{ a_i, a_{i+1}, \dots, a_j \}\). Let \(X_{i,j}\) be a discrete random variable with value \(0\) or \(1\) that indicates whether \(a_i\) and \(a_j\) are compared during the sort.
Clearly the pivots chosen are all different, and elements are compared only with pivots, so the number of distinct pairs compared is
By linearity of expectation,
Lemma 2: \(a_i\) and \(a_j\) are compared if and only if \(a_i\) or \(a_j\) is the first element of the set \(A_{i,j}\) to be chosen as a pivot.
We first prove necessity: if neither \(a_i\) nor \(a_j\) is the first element of \(A_{i,j}\) to be chosen as a pivot, then \(a_i\) and \(a_j\) are not compared.
If neither \(a_i\) nor \(a_j\) is the first element of \(A_{i,j}\) to be chosen as a pivot, there must be an \(x\) with \(i < x < j\) such that \(a_x\) is. The partition around \(a_x\) puts \(a_i\) and \(a_j\) into two different subsequences of the array, so they are never compared afterwards. And since elements are compared only with pivots, \(a_i\) and \(a_j\) were not compared before or during this partition either. Hence \(a_i\) and \(a_j\) are not compared.
Next we prove sufficiency: if \(a_i\) or \(a_j\) is the first element of \(A_{i,j}\) to be chosen as a pivot, then \(a_i\) and \(a_j\) are compared.
Without loss of generality, assume that \(a_i\) is the first element of \(A_{i,j}\) to be chosen as a pivot. No other number of \(A_{i,j}\) has been chosen as a pivot before it, so the elements of \(A_{i,j}\) all lie in the same subsequence of the array. The partition around \(a_i\) compares \(a_i\) with every element of the current subsequence, so \(a_i\) and \(a_j\) are compared.
Now we compute \(P(a_i\ \text{and}\ a_j\ \text{are compared})\). Until some element of \(A_{i,j}\) is chosen as a pivot, the elements of \(A_{i,j}\) all lie in the same subsequence of the array, so each of them is equally likely to be the first one chosen. Since \(A_{i,j}\) has \(j - i + 1\) elements, Lemma 2 gives
Therefore
So the expected time complexity of quicksort is \(O(n \log n)\).
Choosing the pivot at random lowers the probability of running into the worst-case partition. Quicksort's memory accesses also follow the principle of locality, which helps it perform well in practice.1
Optimization
Simple optimization ideas
If you implement quicksort from the basic idea above alone (or copy a template verbatim), you will generally not pass the template problem P1177 [Template] Quicksort, because test data can be constructed that makes naive quicksort degrade to \(O(n^2)\).
So the naive quicksort has to be improved. Three optimizations are fairly common2.
- Choose the element that separates the two subsequences (the pivot, against which the others are compared) by the median of three (that is, the median of the first, the last and the middle element). This avoids the degradation caused by extreme data such as ascending or descending sequences.
- When the sequence is short, insertion sort is more efficient.
- After each pass, gather the elements equal to the pivot around the pivot. This avoids the degradation caused by extreme data such as sequences in which most elements are equal.
A few well-established ways of optimizing quicksort are listed below.
Three-way quicksort
Definition
Three-way quicksort divides the elements into three parts according to how they compare with the pivot. The idea is based on the solution to the Dutch national flag problem.
Procedure
Unlike the original quicksort, three-way quicksort chooses a pivot \(m\) at random and then partitions the sequence to be sorted into three parts: less than \(m\), equal to \(m\) and greater than \(m\). This achieves the effect described above: the elements equal to the pivot are gathered around it.
Properties
On arrays with many repeated values, three-way quicksort is far more efficient than the original quicksort. Its best-case time complexity is \(O(n)\).
Implementation
Three-way quicksort is very simple to implement. A reference implementation follows.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | |
Introsort
Definition
Introsort (introspective sort)3 combines quicksort with heapsort. It was invented by David Musser in 1997. Introsort is really an optimization of quicksort that guarantees a worst-case time complexity of \(O(n\log n)\).
Properties
Introsort limits the partitioning depth of quicksort, usually to \(2\lfloor \log_2n \rfloor\)4, and switches to heapsort once the limit is exceeded. This keeps the locality of quicksort's memory accesses while preventing quicksort from degrading to \(O(n^2)\) in some cases.
Implementation
Since June 2000, the sort() function in stl_algo.h of the SGI C++ STL has been implemented with introsort.
Finding the element with sorted index k in linear time
In the code samples below, the element with sorted index \(k\) is defined as the element at position \(k\) (counting from 0) once the sequence is arranged in ascending order.
The simplest way to find the element with sorted index \(k\) (the \(k\)-th order statistic) is to sort first and then read off the element at that position. This takes \(O(n\log n)\) time, which is wasteful for this problem.
We can solve this problem with the idea behind quicksort. Consider quicksort's partition step: when it finishes, the sequence \(A_{p} \cdots A_{r}\) has been split into \(A_{p} \cdots A_{q}\) and \(A_{q+1} \cdots A_{r}\). Comparing the number of elements on the left (\(q - p + 1\)) with \(k\) then tells us whether to recurse only on the left or only on the right.
As with quicksort, the running time of this method depends on the pivot chosen at each partition. If pivots are chosen at random, the program can be shown to run in expected \(O(n)\) time.
Reference implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | |
Median of medians
Median of medians is a deterministic way of choosing the pivot for partitioning. With it, the algorithm for finding the element with sorted index \(k\) runs in linear time even in the worst case.
The algorithm works as follows:
- Divide the sequence into \(\lceil n/5\rceil\) groups of at most five elements each, keeping the last group even if it has fewer than five;
- Sort each group and take its median, always the lower median when the length is even;
- Recursively select the median of these medians as the pivot, partition three ways into elements less than, equal to and greater than the pivot, and recurse only into the strictly-less or strictly-greater range that contains the target.
Proof of the time complexity
Let \(g=\lceil n/5\rceil\) be the number of group medians. On each side of the pivot (equality included) there are at least \(\lfloor g/2\rfloor\) group medians; leaving the last group aside, every full group contributes at least three elements that are no greater than, or no less than, the pivot. So each side has at least \(3n/10-O(1)\) such elements, and the strictly-less and strictly-greater ranges each have size at most \(7n/10+O(1)\). The range of elements equal to the pivot is not recursed into. Grouping, finding the median of each group and partitioning cost \(O(n)\) in total. Altogether, we get the inequality
Take fixed constants \(a\) and \(b\) such that the two recursive sizes on the right sum to at most \(9n/10+a\) and the non-recursive cost is at most \(bn\). When \(n\ge20a\), this sum is at most \(19n/20\). Under the induction hypothesis \(T(m)\le cm\), it is enough to take \(c\ge20b\), and to increase \(c\) until it covers the finitely many base cases, to get \(T(n)\le19cn/20+bn\le cn\). The worst-case time complexity is therefore \(O(n)\).
References and notes
-
The C++ Performance Juicer: The Principle of Locality - I'm Root lee ! (in Chinese) ↩
-
Three Kinds of Quicksort and Optimizations of Quicksort (in Chinese) ↩
-
For example, libstdc++ 14.2.0:
__introsort_loopand__sort. In fact, limiting the depth to \(O(\log n)\) and switching to heapsort when the limit is reached is enough to guarantee a total time complexity of \(O(n\log n)\). ↩ -
Algorithm Implementation/Sorting/Quicksort - Wikibooks, the free textbook (in Chinese) ↩↩↩
This page is an unofficial English translation of the original OI Wiki page (revision b469442a), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: partychicken, 24OI-bot, billchenchina, ouuan, sshwy, Konano, ksyx, NachtgeistW, Backl1ght, Xeonacid, StudyingFather, sbofgayschool, Enter-tainer, xzcxzcyy, iamtwz, mcendu, Alisahhh, Ir1d, zhangjunyan2580, zirnc, Menci, untitledunrevised, shawlleyw, PhantomPower82, weilycoder, wpcwzy, ZnPdCo, Tiphereth-A, c-forrest (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.