Quicksort


Quicksort is an efficient sorting algorithm. Developed by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting. When implemented well, it can be about two or three times faster than its main competitors, merge sort and heapsort.
Quicksort is a divide-and-conquer algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. This can be done in-place, requiring small additional amounts of memory to perform the sorting.
Quicksort is a comparison sort, meaning that it can sort items of any type for which a "less-than" relation is defined. Efficient implementations of Quicksort are not a stable sort, meaning that the relative order of equal sort items is not preserved.
Mathematical analysis of quicksort shows that, on average, the algorithm takes O comparisons to sort n items. In the worst case, it makes O comparisons, though this behavior is rare.

History

The quicksort algorithm was developed in 1959 by Tony Hoare while in the Soviet Union, as a visiting student at Moscow State University. At that time, Hoare worked on a project on machine translation for the National Physical Laboratory. As a part of the translation process, he needed to sort the words in Russian sentences prior to looking them up in a Russian-English dictionary that was already sorted in alphabetic order on magnetic tape. After recognizing that his first idea, insertion sort, would be slow, he quickly came up with a new idea that was Quicksort. He wrote a program in Mercury Autocode for the partition but could not write the program to account for the list of unsorted segments. On return to England, he was asked to write code for Shellsort as part of his new job. Hoare mentioned to his boss that he knew of a faster algorithm and his boss bet sixpence that he did not. His boss ultimately accepted that he had lost the bet. Later, Hoare learned about ALGOL and its ability to do recursion that enabled him to publish the code in Communications of the Association for Computing Machinery, the premier computer science journal of the time.
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 Ph.D. 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 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 runtime when all elements are equal.
In 2009, Vladimir Yaroslavskiy proposed the new dual pivot Quicksort implementation. In the Java core library mailing lists, he initiated a discussion claiming his new algorithm to be superior to the runtime library's sorting method, which was at that time based on the widely used and carefully tuned variant of classic Quicksort by Bentley and McIlroy. Yaroslavskiy's Quicksort has been chosen as the new default sorting algorithm in Oracle's Java 7 runtime library after extensive empirical performance tests.

Algorithm

Quicksort is a divide and conquer algorithm. It first divides the input array into two smaller sub-arrays: the low elements and the high elements. It then recursively sorts the sub-arrays. The steps for in-place Quicksort are:
  1. Pick an element, called a pivot, from the array.
  2. Partitioning: reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it. After this partitioning, the pivot is in its final position. This is called the partition operation.
  3. Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.
The base case of the recursion is arrays of size zero or one, which are in order by definition, so they never need to be sorted.
The pivot selection and partitioning steps can be done in several different ways; the choice of specific implementation schemes greatly affects the algorithm's performance.

Lomuto partition scheme

This scheme is attributed to Nico Lomuto and popularized by Bentley in his book Programming Pearls and Cormen et al. in their book Introduction to Algorithms. This scheme chooses a pivot that is typically the last element in the array. The algorithm maintains index as it scans the array using another index such that the elements at through are less than the pivot, and the elements at through are equal to or greater than the pivot. As this scheme is more compact and easy to understand, it is frequently used in introductory material, although it is less efficient than Hoare's original scheme e.g., when all elements are equal. This scheme degrades to when the array is already in order. There have been various variants proposed to boost performance including various ways to select pivot, deal with equal elements, use other sorting algorithms such as Insertion sort for small arrays and so on. In pseudocode, a quicksort that sorts elements at through of an array can be expressed as:
algorithm quicksort is
if lo < hi then
p := partition
quicksort
quicksort
algorithm partition is
pivot := A
i := lo
for j := lo to hi do
if A < pivot then
swap A with A
i := i + 1
swap A with A
return i
Sorting the entire array is accomplished by.

Hoare partition scheme

The original partition scheme described by C.A.R. Hoare uses two indices that start at the ends of the array being partitioned, then move toward each other, until they detect an inversion: a pair of elements, one greater than or equal to the pivot, one less than or equal, that are in the wrong order relative to each other. The inverted elements are then swapped. When the indices meet, the algorithm stops and returns the final index. Hoare's scheme is more efficient than Lomuto's partition scheme because it does three times fewer swaps on average, and it creates efficient partitions even when all values are equal. Like Lomuto's partition scheme, Hoare's partitioning also would cause Quicksort to degrade to for already sorted input, if the pivot was chosen as the first or the last element. With the middle element as the pivot, however, sorted data results with no swaps in equally sized partitions leading to best case behavior of Quicksort, i.e.. Like others, Hoare's partitioning doesn't produce a stable sort. In this scheme, the pivot's final location is not necessarily at the index that is returned, as the pivot and elements equal to the pivot can end up anywhere within the partition after a partition step, and may not be sorted until the base case of a partition with a single element is reached via recursion. The next two segments that the main algorithm recurs on are and as opposed to and as in Lomuto's scheme. However, the partitioning algorithm guarantees which implies both resulting partitions are non-empty, hence there's no risk of infinite recursion. In pseudocode,
algorithm quicksort is
if lo < hi then
p := partition
quicksort
quicksort
algorithm partition is
pivot := A
i := lo - 1
j := hi + 1
loop forever
do
i := i + 1
while A < pivot
do
j := j - 1
while A > pivot
if i ≥ j then
return j
swap A with A
An important point in choosing the pivot item is to round the division result towards zero. This is the implicit behavior of integer division in some programming languages, hence rounding is omitted in implementing code. Here it is emphasized with explicit use of a floor function, denoted with a symbols pair. Rounding down is important to avoid using A as the pivot, which can result in infinite recursion.
The entire array is sorted by.

Implementation issues

Choice of pivot

In the very early versions of quicksort, the leftmost element of the partition would often be chosen as the pivot element. Unfortunately, this causes worst-case behavior on already sorted arrays, which is a rather common use-case. The problem was easily solved by choosing either a random index for the pivot, choosing the middle index of the partition or choosing the median of the first, middle and last element of the partition for the pivot. This "median-of-three" rule counters the case of sorted input, and gives a better estimate of the optimal pivot than selecting any single element, when no information about the ordering of the input is known.
Median-of-three code snippet for Lomuto partition:
mid := / 2
if A < A
swap A with A
if A < A
swap A with A
if A < A
swap A with A
pivot := A
It puts a median into A first, then that new value of A is used for a pivot, as in a basic algorithm presented above.
Specifically, the expected number of comparisons needed to sort elements with random pivot selection is. Median-of-three pivoting brings this down to, at the expense of a three-percent increase in the expected number of swaps. An even stronger pivoting rule, for larger arrays, is to pick the ninther, a recursive median-of-three, defined as
Selecting a pivot element is also complicated by the existence of integer overflow. If the boundary indices of the subarray being sorted are sufficiently large, the naïve expression for the middle index,, will cause overflow and provide an invalid pivot index. This can be overcome by using, for example, to index the middle element, at the cost of more complex arithmetic. Similar issues arise in some other methods of selecting the pivot element.

Repeated elements

With a partitioning algorithm such as the Lomuto partition scheme described above, quicksort exhibits poor performance for inputs that contain many repeated elements. The problem is clearly apparent when all the input elements are equal: at each recursion, the left partition is empty, and the right partition has only decreased by one element. Consequently, the Lomuto partition scheme takes quadratic time to sort an array of equal values. However, with a partitioning algorithm such as the Hoare partition scheme, repeated elements generally results in better partitioning, and although needless swaps of elements equal to the pivot may occur, the running time generally decreases as the number of repeated elements increases. In the case where all elements are equal, Hoare partition scheme needlessly swaps elements, but the partitioning itself is best case, as noted in the Hoare partition section above.
To solve the Lomuto partition scheme problem, an alternative linear-time partition routine can be used that separates the values into three groups: values less than the pivot, values equal to the pivot, and values greater than the pivot. The values equal to the pivot are already sorted, so only the less-than and greater-than partitions need to be recursively sorted. In pseudocode, the quicksort algorithm becomes
algorithm quicksort is
if lo < hi then
p := pivot
left, right := partition // note: multiple return values
quicksort
quicksort
The partition algorithm returns indices to the first and to the last item of the middle partition. Every item of the partition is equal to p and is therefore sorted. Consequently, the items of the partition need not be included in the recursive calls to quicksort.
The best case for the algorithm now occurs when all elements are equal. In the case of all equal elements, the modified quicksort will perform only two recursive calls on empty subarrays and thus finish in linear time.

Optimizations

Two other important optimizations, also suggested by Sedgewick and widely used in practice, are:
Quicksort's divide-and-conquer formulation makes it amenable to parallelization using task parallelism. The partitioning step is accomplished through the use of a parallel prefix sum algorithm to compute an index for each array element in its section of the partitioned array. Given an array of size, the partitioning step performs work in time and requires additional scratch space. After the array has been partitioned, the two partitions can be sorted recursively in parallel. Assuming an ideal choice of pivots, parallel quicksort sorts an array of size in work in time using additional space.
Quicksort has some disadvantages when compared to alternative sorting algorithms, like merge sort, which complicate its efficient parallelization. The depth of quicksort's divide-and-conquer tree directly impacts the algorithm's scalability, and this depth is highly dependent on the algorithm's choice of pivot. Additionally, it is difficult to parallelize the partitioning step efficiently in-place. The use of scratch space simplifies the partitioning step, but increases the algorithm's memory footprint and constant overheads.
Other more sophisticated parallel sorting algorithms can achieve even better time bounds. For example, in 1991 David Powers described a parallelized quicksort that can operate in time on a CRCW PRAM with processors by performing partitioning implicitly.

Formal analysis

Worst-case analysis

The most unbalanced partition occurs when one of the sublists returned by the partitioning routine is of size. This may occur if the pivot happens to be the smallest or largest element in the list, or in some implementations when all the elements are equal.
If this happens repeatedly in every partition, then each recursive call processes a list of size one less than the previous list. Consequently, we can make nested calls before we reach a list of size 1. This means that the call tree is a linear chain of nested calls. The th call does work to do the partition, and, so in that case Quicksort takes time.

Best-case analysis

In the most balanced case, each time we perform a partition we divide the list into two nearly equal pieces. This means each recursive call processes a list of half the size. Consequently, we can make only nested calls before we reach a list of size 1. This means that the depth of the call tree is. But no two calls at the same level of the call tree process the same part of the original list; thus, each level of calls needs only time all together. The result is that the algorithm uses only time.

Average-case analysis

To sort an array of distinct elements, quicksort takes time in expectation, averaged over all permutations of elements with equal probability. We list here three common proofs to this claim providing different insights into quicksort's workings.

Using percentiles

If each pivot has rank somewhere in the middle 50 percent, that is, between the 25th percentile and the 75th percentile, then it splits the elements with at least 25% and at most 75% on each side. If we could consistently choose such pivots, we would only have to split the list at most times before reaching lists of size 1, yielding an algorithm.
When the input is a random permutation, the pivot has a random rank, and so it is not guaranteed to be in the middle 50 percent. However, when we start from a random permutation, in each recursive call the pivot has a random rank in its list, and so it is in the middle 50 percent about half the time. That is good enough. Imagine that a coin is flipped: heads means that the rank of the pivot is in the middle 50 percent, tail means that it isn't. Now imagine that the coin is flipped over and over until it gets heads. Although this could take a long time, on average only flips are required, and the chance that the coin won't get heads after flips is highly improbable. By the same argument, Quicksort's recursion will terminate on average at a call depth of only. But if its average call depth is, and each level of the call tree processes at most elements, the total amount of work done on average is the product,. The algorithm does not have to verify that the pivot is in the middle half—if we hit it any constant fraction of the times, that is enough for the desired complexity.

Using recurrences

An alternative approach is to set up a recurrence relation for the factor, the time needed to sort a list of size. In the most unbalanced case, a single quicksort call involves work plus two recursive calls on lists of size and, so the recurrence relation is
This is the same relation as for insertion sort and selection sort, and it solves to worst case.
In the most balanced case, a single quicksort call involves work plus two recursive calls on lists of size, so the recurrence relation is
The master theorem for divide-and-conquer recurrences tells us that.
The outline of a formal proof of the expected time complexity follows. Assume that there are no duplicates as duplicates could be handled with linear time pre- and post-processing, or considered cases easier than the analyzed. When the input is a random permutation, the rank of the pivot is uniform random from 0 to. Then the resulting parts of the partition have sizes and, and i is uniform random from 0 to. So, averaging over all possible splits and noting that the number of comparisons for the partition is, the average number of comparisons over all permutations of the input sequence can be estimated accurately by solving the recurrence relation:
Solving the recurrence gives.
This means that, on average, quicksort performs only about 39% worse than in its best case. In this sense, it is closer to the best case than the worst case. A comparison sort cannot use less than comparisons on average to sort items and in case of large, Stirling's approximation yields, so quicksort is not much worse than an ideal comparison sort. This fast average runtime is another reason for quicksort's practical dominance over other sorting algorithms.

Using a binary search tree

To each execution of quicksort corresponds the following binary search tree : the initial pivot is the root node; the pivot of the left half is the root of the left subtree, the pivot of the right half is the root of the right subtree, and so on. The number of comparisons of the execution of quicksort equals the number of comparisons during the construction of the BST by a sequence of insertions. So, the average number of comparisons for randomized quicksort equals the average cost of constructing a BST when the values inserted form a random permutation.
Consider a BST created by insertion of a sequence of values forming a random permutation. Let denote the cost of creation of the BST. We have, where is an binary random variable expressing whether during the insertion of there was a comparison to.
By linearity of expectation, the expected value of is.
Fix and. The values, once sorted, define intervals. The core structural observation is that is compared to in the algorithm if and only if falls inside one of the two intervals adjacent to.
Observe that since is a random permutation, is also a random permutation, so the probability that is adjacent to is exactly.
We end with a short calculation:

Space complexity

The space used by quicksort depends on the version used.
The in-place version of quicksort has a space complexity of, even in the worst case, when it is carefully implemented using the following strategies:
Quicksort with in-place and unstable partitioning uses only constant additional space before making any recursive call. Quicksort must store a constant amount of information for each nested recursive call. Since the best case makes at most nested recursive calls, it uses space. However, without Sedgewick's trick to limit the recursive calls, in the worst case quicksort could make nested recursive calls and need auxiliary space.
From a bit complexity viewpoint, variables such as lo and hi do not use constant space; it takes bits to index into a list of items. Because there are such variables in every stack frame, quicksort using Sedgewick's trick requires bits of space. This space requirement isn't too terrible, though, since if the list contained distinct elements, it would need at least bits of space.
Another, less common, not-in-place, version of quicksort uses space for working storage and can implement a stable sort. The working storage allows the input array to be easily partitioned in a stable manner and then copied back to the input array for successive recursive calls. Sedgewick's optimization is still appropriate.

Relation to other algorithms

Quicksort is a space-optimized version of the binary tree sort. Instead of inserting items sequentially into an explicit tree, quicksort organizes them concurrently into a tree that is implied by the recursive calls. The algorithms make exactly the same comparisons, but in a different order. An often desirable property of a sorting algorithm is stability – that is the order of elements that compare equal is not changed, allowing controlling order of multikey tables in a natural way. This property is hard to maintain for in situ quicksort. For variant quicksorts involving extra memory due to representations using pointers or files, it is trivial to maintain stability. The more complex, or disk-bound, data structures tend to increase time cost, in general making increasing use of virtual memory or disk.
The most direct competitor of quicksort is heapsort. Heapsort's running time is, but heapsort's average running time is usually considered slower than in-place quicksort. This result is debatable; some publications indicate the opposite. Introsort is a variant of quicksort that switches to heapsort when a bad case is detected to avoid quicksort's worst-case running time.
Quicksort also competes with merge sort, another sorting algorithm. Mergesort is a stable sort, unlike standard in-place quicksort and heapsort, and has excellent worst-case performance. The main disadvantage of mergesort is that, when operating on arrays, efficient implementations require auxiliary space, whereas the variant of quicksort with in-place partitioning and tail recursion uses only space.
Mergesort works very well on linked lists, requiring only a small, constant amount of auxiliary storage. Although quicksort can be implemented as a stable sort using linked lists, it will often suffer from poor pivot choices without random access. Mergesort is also the algorithm of choice for external sorting of very large data sets stored on slow-to-access media such as disk storage or network-attached storage.
Bucket sort with two buckets is very similar to quicksort; the pivot in this case is effectively the value in the middle of the value range, which does well on average for uniformly distributed inputs.

Selection-based pivoting

A selection algorithm chooses the th smallest of a list of numbers; this is an easier problem in general than sorting. One simple but effective selection algorithm works nearly in the same manner as quicksort, and is accordingly known as quickselect. The difference is that instead of making recursive calls on both sublists, it only makes a single tail-recursive call on the sublist that contains the desired element. This change lowers the average complexity to linear or time, which is optimal for selection, but the sorting algorithm is still.
A variant of quickselect, the median of medians algorithm, chooses pivots more carefully, ensuring that the pivots are near the middle of the data, and thus has guaranteed linear time –. This same pivot strategy can be used to construct a variant of quicksort with time. However, the overhead of choosing the pivot is significant, so this is generally not used in practice.
More abstractly, given an selection algorithm, one can use it to find the ideal pivot at every step of quicksort and thus produce a sorting algorithm with running time. Practical implementations this variant are considerably slower on average, but they are of theoretical interest because they show an optimal selection algorithm can yield an optimal sorting algorithm.

Variants

Multi-pivot quicksort

Instead of partitioning into two subarrays using a single pivot, multi-pivot quicksort partitions its input into some number of subarrays using pivots. While the dual-pivot case was considered by Sedgewick and others already in the mid-1970s, the resulting algorithms were not faster in practice than the "classical" quicksort. A 1999 assessment of a multiquicksort with a variable number of pivots, tuned to make efficient use of processor caches, found it to increase the instruction count by some 20%, but simulation results suggested that it would be more efficient on very large inputs. A version of dual-pivot quicksort developed by Yaroslavskiy in 2009 turned out to be fast enough to warrant implementation in Java 7, as the standard algorithm to sort arrays of primitives. The performance benefit of this algorithm was subsequently found to be mostly related to cache performance, and experimental results indicate that the three-pivot variant may perform even better on modern machines.

External quicksort

For disk files, an external sort based on partitioning similar to quicksort is possible. It is slower than external merge sort, but doesn't require extra disk space. 4 buffers are used, 2 for input, 2 for output. Let N = number of records in the file, B = the number of records per buffer, and M = N/B = the number of buffer segments in the file. Data is read from both ends of the file inwards. Let X represent the segments that start at the beginning of the file and Y represent segments that start at the end of the file. Data is read into the X and Y read buffers. A pivot record is chosen and the records in the X and Y buffers other than the pivot record are copied to the X write buffer in ascending order and Y write buffer in descending order based comparison with the pivot record. Once either X or Y buffer is filled, it is written to the file and the next X or Y buffer is read from the file. The process continues until all segments are read and one write buffer remains. If that buffer is an X write buffer, the pivot record is appended to it and the X buffer written. If that buffer is a Y write buffer, the pivot record is prepended to the Y buffer and the Y buffer written. This constitutes one partition step of the file, and the file is now composed of two subfiles. The start and end positions of each subfile are pushed/popped to a stand-alone stack or the main stack via recursion. To limit stack space to O, the smaller subfile is processed first. For a stand-alone stack, push the larger subfile parameters onto the stack, iterate on the smaller subfile. For recursion, recurse on the smaller subfile first, then iterate to handle the larger subfile. One a sub-file is less than or equal to 4 B records, the subfile is sorted in place via quicksort and written. That subfile is now sorted and in place in the file. The process is continued until all sub-files are sorted and in place. The average number of passes on the file is approximately 1 + ln/, but worst case pattern is N passes.

Three-way radix quicksort

This algorithm is a combination of radix sort and quicksort. Pick an element from the array and consider the first character of the string. Partition the remaining elements into three sets: those whose corresponding character is less than, equal to, and greater than the pivot's character. Recursively sort the "less than" and "greater than" partitions on the same character. Recursively sort the "equal to" partition by the next character. Given we sort using bytes or words of length bits, the best case is and the worst case or at least as for standard quicksort, given for unique keys, and is a hidden constant in all standard comparison sort algorithms including quicksort. This is a kind of three-way quicksort in which the middle partition represents a sorted subarray of elements that are exactly equal to the pivot.

Quick radix sort

Also developed by Powers as an parallel PRAM algorithm. This is again a combination of radix sort and quicksort but the quicksort left/right partition decision is made on successive bits of the key, and is thus for -bit keys. All comparison sort algorithms impliclty assume the transdichotomous model with in, as if is smaller we can sort in time using a hash table or integer sorting. If but elements are unique within bits, the remaining bits will not be looked at by either quicksort or quick radix sort. Failing that, all comparison sorting algorithms will also have the same overhead of looking through relatively useless bits but quick radix sort will avoid the worst case behaviours of standard quicksort and radix quicksort, and will be faster even in the best case of those comparison algorithms under these conditions of. See Powers for further discussion of the hidden overheads in comparison, radix and parallel sorting.

BlockQuicksort

In any comparison-based sorting algorithm, minimizing the number of comparisons requires maximizing the amount of information gained from each comparison, meaning that the comparison results are unpredictable. This causes frequent branch mispredictions, limiting performance. BlockQuicksort rearranges the computations of quicksort to convert unpredictable branches to data dependencies. When partitioning, the input is divided into moderate-sized blocks, and two arrays are filled with the positions of elements to swap. A second pass exchanges the elements at the positions indicated in the arrays. Both loops have only one conditional branch, a test for termination, which is usually taken.

Partial and incremental quicksort

Several variants of quicksort exist that separate the smallest or largest elements from the rest of the input.

Generalization

and David C. Kandathil, in 2004, discovered a one-parameter family of sorting algorithms, called partition sorts, which on average perform at most comparisons and operations; at worst they perform comparisons ; these are in-place, requiring only additional space. Practical efficiency and smaller variance in performance were demonstrated against optimised quicksorts.