{"history":[],"article":{"id":"1a499f15-0c29-4881-a0df-9d783f3c11af","title":"Quicksort","slug":"quicksort","content":":::summary\n**Class:** [Sorting algorithm](https://bliptext.com/articles/sorting-algorithm) \n**Time:** O(n^2) \n**Average -time:** O(n\\log n) \n**Best -time:** O(n\\log n) (simple partition) · or O(n) (three-way partition and equal keys) \n**Space:** O(n) auxiliary (naive) · O(\\log n) auxiliary (Hoare 1962) \n**Optimal:** No \n**Stability:** [Not Stable](https://bliptext.com/articles/sorting-algorithm) \n:::\n\n# \n**Quicksort** is an efficient, general-purpose [sorting algorithm](https://bliptext.com/articles/sorting-algorithm).\nQuicksort was developed by British computer scientist [Tony Hoare](https://bliptext.com/articles/tony-hoare) in 1959 and published in 1961.\nIt is still a commonly used algorithm for sorting.\nOverall, it is slightly faster than [merge sort](https://bliptext.com/articles/merge-sort) and [heapsort](https://bliptext.com/articles/heapsort) for randomized data, particularly on larger distributions.\nQuicksort is a [divide-and-conquer algorithm](https://bliptext.com/articles/divide-and-conquer-algorithm).\nIt 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.\nFor this reason, it is sometimes called **partition-exchange sort**.\nThe sub-arrays are then sorted [recursively](https://bliptext.com/articles/recursion-computer-science).\nThis can be done [in-place](https://bliptext.com/articles/in-place-algorithm), requiring small additional amounts of [memory](https://bliptext.com/articles/main-memory) to perform the sorting.\nQuicksort is a [comparison sort](https://bliptext.com/articles/comparison-sort), meaning that it can sort items of any type for which a \"less-than\" relation (formally, a [total order](https://bliptext.com/articles/total-order)) is defined.\nIt is a comparison-based sort since elements a and b are only swapped in case their relative order has been obtained in the transitive closure of prior comparison-outcomes.\nMost implementations of quicksort are not [stable](https://bliptext.com/articles/sorting-algorithm), meaning that the relative order of equal sort items is not preserved.\n[Mathematical analysis](https://bliptext.com/articles/analysis-of-algorithms) of quicksort shows that, [on average](https://bliptext.com/articles/best-worst-and-average-case), the algorithm takes comparisons to sort n items.\nIn the [worst case](https://bliptext.com/articles/best-worst-and-average-case), it makes O(n^2) comparisons.\n\n# History\nThe quicksort algorithm was developed in 1959 by [Tony Hoare](https://bliptext.com/articles/tony-hoare) while he was a visiting student at [Moscow State University](https://bliptext.com/articles/moscow-state-university).\nAt that time, Hoare was working on a [machine translation](https://bliptext.com/articles/machine-translation) project for the [National Physical Laboratory](https://bliptext.com/articles/national-physical-laboratory-uk).\nAs 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](https://bliptext.com/articles/magnetic-tape-data-storage).\nAfter recognizing that his first idea, [insertion sort](https://bliptext.com/articles/insertion-sort), would be slow, he came up with a new idea.\nHe wrote the partition part in Mercury [Autocode](https://bliptext.com/articles/autocode) but had trouble dealing with the list of unsorted segments.\nOn return to England, he was asked to write code for [Shellsort](https://bliptext.com/articles/shellsort).\nHoare mentioned to his boss that he knew of a faster algorithm and his boss bet a [sixpence](https://bliptext.com/articles/sixpence-british-coin) that he did not.\nHis boss ultimately accepted that he had lost the bet.\nHoare published a paper about his algorithm in [The Computer Journal](https://bliptext.com/articles/the-computer-journal) [Volume 5, Issue 1, 1962, Pages 10–16](https://bliptext.com/articles/undefined).\nLater, Hoare learned about [ALGOL](https://bliptext.com/articles/algol) and its ability to do recursion that enabled him to publish an improved version of the algorithm in [ALGOL](https://bliptext.com/articles/algol) in [Communications of the Association for Computing Machinery](https://bliptext.com/articles/communications-of-the-acm), the premier computer science journal of the time.\nThe 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](https://bliptext.com/articles/undefined).\nQuicksort gained widespread adoption, appearing, for example, in [Unix](https://bliptext.com/articles/unix) as the default library sort subroutine.\nHence, it lent its name to the [C standard library](https://bliptext.com/articles/c-standard-library) subroutine qsort and in the reference implementation of [Java](https://bliptext.com/articles/java-programming-language).\n[Robert Sedgewick](https://bliptext.com/articles/robert-sedgewick-computer-scientist)'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](https://bliptext.com/articles/samplesort), adaptive partitioning by Van Emden as well as derivation of expected number of comparisons and swaps.\n[Jon Bentley](https://bliptext.com/articles/jon-bentley-computer-scientist) and [Doug McIlroy](https://bliptext.com/articles/douglas-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.\nBentley described another simpler and compact partitioning scheme in his book Programming Pearls that he attributed to [Nico Lomuto](https://bliptext.com/articles/nico-lomuto).\nLater 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.\nBentley described Quicksort as the \"most beautiful code I had ever written\" in the same essay.\nLomuto's partition scheme was also popularized by the textbook [Introduction to Algorithms](https://bliptext.com/articles/introduction-to-algorithms) although it is inferior to Hoare's scheme because it does three times more swaps on average and degrades to\nO(n2)\nruntime when all elements are equal.\nMcIlroy 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.\n\n# Algorithm\n[[File:Quicksort-diagram.svg|right|200px|thumb|Full example of quicksort on a random set of numbers. The shaded element is the pivot. It is always chosen as the last element of the partition. However, always choosing the last element in the partition as the pivot in this way results in poor performance (\nO(n2)\n) on already sorted arrays, or arrays of identical elements. Since sub-arrays of sorted / identical elements crop up a lot towards the end of a sorting procedure on a large set, versions of the quicksort algorithm that choose the pivot as the middle element run much more quickly than the algorithm described in this diagram on large sets of numbers.]] Quicksort is a type of [divide-and-conquer algorithm](https://bliptext.com/articles/divide-and-conquer-algorithm) for sorting an array, based on a partitioning routine; the details of this partitioning can vary somewhat, so that quicksort is really a family of closely related algorithms. Applied to a range of at least two elements, partitioning produces a division into two consecutive non empty sub-ranges, in such a way that no element of the first sub-range is greater than any element of the second sub-range. After applying this partition, quicksort then recursively sorts the sub-ranges, possibly after excluding from them an element at the point of division that is at this point known to be already in its final location.\nDue to its recursive nature, quicksort (like the partition routine) has to be formulated so as to be callable for a range within a larger array, even if the ultimate goal is to sort a complete array.\nThe steps for [in-place](https://bliptext.com/articles/in-place-algorithm) quicksort are:\nThe choice of partition routine (including the pivot selection) and other details not entirely specified above can affect the algorithm's performance, possibly to a great extent for specific input arrays.\nIn discussing the efficiency of quicksort, it is therefore necessary to specify these choices first.\nHere we mention two specific partition methods.\n\n## Lomuto partition scheme\nThis 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](https://bliptext.com/articles/introduction-to-algorithms).\nIn most formulations this scheme chooses as the pivot the last element in the array.\nThe algorithm maintains index i as it scans the array using another index j such that the elements at lo through i-1 (inclusive) are less than the pivot, and the elements at i through j (inclusive) are equal to or greater than the pivot.\nAs 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.\nThe complexity of Quicksort with this scheme degrades to\nO(n2)\nwhen the array is already in order, due to the partition being the worst possible one.\nThere have been various variants proposed to boost performance including various ways to select the pivot, deal with equal elements, use other sorting algorithms such as [insertion sort](https://bliptext.com/articles/insertion-sort) for small arrays, and so on.\nIn [pseudocode](https://bliptext.com/articles/pseudocode), a quicksort that sorts elements at lo through hi (inclusive) of an array A can be expressed as:\n// Sorts (a portion of) an array, divides it into partitions, then sorts those\n**algorithm** quicksort(A, lo, hi) **is**\n// Ensure indices are in correct order\n**if** lo >= hi || lo < 0 **then**\nreturn\n// Partition array and get the pivot index\np := partition(A, lo, hi)\n// Sort the two partitions\nquicksort(A, lo, p - 1) // Left side of pivot\nquicksort(A, p + 1, hi) // Right side of pivot\n// Divides array into two partitions\n**algorithm** partition(A, lo, hi) **is**\npivot := A[hi] // Choose the last element as the pivot\n// Temporary pivot index\ni := lo **for** j := lo **to** hi - 1 **do**\n// If the current element is less than or equal to the pivot\n**if** A[j] <= pivot **then**\n// Swap the current element with the element at the temporary pivot index\nswap A[i] **with** A[j]\n// Move the temporary pivot index forward\ni := i + 1\n// Swap the pivot with the last element\nswap A[i] **with** A[hi]\n**return** i // the pivot index\nSorting the entire array is accomplished by quicksort(A, 0, length(A) - 1).\n\n## Hoare partition scheme\nThe original partition scheme described by [Tony Hoare](https://bliptext.com/articles/tony-hoare) uses two pointers (indices into the range) that start at both ends of the array being partitioned, then move toward each other, until they detect an inversion: a pair of elements, one greater than the pivot at the first pointer, and one less than the pivot at the second pointer; if at this point the first pointer is still before the second, these elements are in the wrong order relative to each other, and they are then exchanged.\nAfter this the pointers are moved inwards, and the search for an inversion is repeated; when eventually the pointers cross (the first points after the second), no exchange is performed; a valid partition is found, with the point of division between the crossed pointers (any entries that might be strictly between the crossed pointers are equal to the pivot and can be excluded from both sub-ranges formed).\nWith this formulation it is possible that one sub-range turns out to be the whole original range, which would prevent the algorithm from advancing.\nHoare therefore stipulates that at the end, the sub-range containing the pivot element (which still is at its original position) can be decreased in size by excluding that pivot, after (if necessary) exchanging it with the sub-range element closest to the separation; thus, termination of quicksort is ensured.\nWith respect to this original description, implementations often make minor but important variations.\nNotably, the scheme as presented below includes elements equal to the pivot among the candidates for an inversion (so \"greater than or equal\" and \"less than or equal\" tests are used instead of \"greater than\" and \"less than\" respectively; since the formulation uses do...while rather than repeat...until which is actually reflected by the use of strict comparison operators).\nWhile there is no reason to exchange elements equal to the pivot, this change allows tests on the pointers themselves to be omitted, which are otherwise needed to ensure they do not run out of range.\nIndeed, since at least one instance of the pivot value is present in the range, the first advancement of either pointer cannot pass across this instance if an inclusive test is used; once an exchange is performed, these exchanged elements are now both strictly ahead of the pointer that found them, preventing that pointer from running off.\n(The latter is true independently of the test used, so it would be possible to use the inclusive test only when looking for the first inversion. However, using an inclusive test throughout also ensures that a division near the middle is found when all elements in the range are equal, which gives an important efficiency gain for sorting arrays with many equal elements.) The risk of producing a non-advancing separation is avoided in a different manner than described by Hoare.\nSuch a separation can only result when no inversions are found, with both pointers advancing to the pivot element at the first iteration (they are then considered to have crossed, and no exchange takes place).\nIn [pseudocode](https://bliptext.com/articles/pseudocode),\n// Sorts (a portion of) an array, divides it into partitions, then sorts those\n**algorithm** quicksort(A, lo, hi) **is**\n**if** lo >= 0 && hi >= 0 && lo < hi **then**\np := partition(A, lo, hi)\nquicksort(A, lo, p) // Note: the pivot is now included\nquicksort(A, p + 1, hi)\n// Divides array into two partitions\n**algorithm** partition(A, lo, hi) **is**\n// Pivot value\npivot := A[lo] // Choose the first element as the pivot\n// Left index\ni := lo - 1\n// Right index\nj := hi + 1\n**loop forever**\n// Move the left index to the right at least once and while the element at\n// the left index is less than the pivot\n**do** i := i + 1 **while** A[i] < pivot\n// Move the right index to the left at least once and while the element at\n// the right index is greater than the pivot\n**do** j := j - 1 **while** A[j] > pivot\n// If the indices crossed, return\n**if** i >= j **then** **return** j // Swap the elements at the left and right indices\n**swap** A[i] **with** A[j]\nThe entire array is sorted by quicksort(A, 0, length(A) - 1).\nHoare's scheme is more efficient than Lomuto's partition scheme because it does three times fewer swaps on average.\nAlso, as mentioned, the implementation given creates a balanced partition even when all values are equal.\n, which Lomuto's scheme does not.\nLike Lomuto's partition scheme, Hoare's partitioning also would cause Quicksort to degrade to\nO(n2)\nfor already sorted input, if the pivot was chosen as the first or the last element.\nWith the middle element as the pivot, however, sorted data results with (almost) no swaps in equally sized partitions leading to best case behavior of Quicksort, i.e.\nO(n log(n))\n. Like others, Hoare's partitioning doesn't produce a stable sort.\nIn 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.\nTherefore, the next two segments that the main algorithm recurs on are (lo..p) (elements ≤ pivot) and (p+1..hi) (elements ≥ pivot) as opposed to (lo..p-1) and (p+1..hi) as in Lomuto's scheme.\n**Subsequent recursions (expansion on previous paragraph)**\nLet's expand a little bit on the next two segments that the main algorithm recurs on.\nBecause we are using strict comparators (>, <) in the **\"do...while\"** loops to prevent ourselves from running out of range, there's a chance that the pivot itself gets swapped with other elements in the partition function.\nTherefore, **the index returned in the partition function isn't necessarily where the actual pivot is.** Consider the example of **[5, 2, 3, 1, 0]**, following the scheme, after the first partition the array becomes **[0, 2, 1, 3, 5]**, the \"index\" returned is 2, which is the number 1, when the real pivot, the one we chose to start the partition with was the number 3.\nWith this example, we see how it is necessary to include the returned index of the partition function in our subsequent recursions.\nAs a result, we are presented with the choices of either recursing on (lo..p) and (p+1..hi), or (lo..p - 1) and (p..hi).\nWh**i**ch of the two opt**i**ons we choose depends on wh**i**ch **i**ndex (**i** or **j**) we return **i**n the part**i**t**i**on funct**i**on when the **i**nd**i**ces cross, and how we choose our p**i**vot **i**n the part**i**t**i**on funct**i**on (**floor** v.s. ce**i**l**i**ng).\nLet's first examine the choice of recursing on (lo..p) and (p+1..hi), with the example of sorting an array where multiple identical elements exist **[0, 0]**.\nIf index i (the \"latter\" index) is returned after indices cross in the partition function, the index 1 would be returned after the first partition.\nThe subsequent recursion on (lo..p)would be on (0, 1), which corresponds to the exact same array **[0, 0]**.\nA non-advancing separation that causes infinite recursion is produced.\nIt is therefore obvious that **when recursing on **(lo..p)** and (p+1..hi), because the left half of the recursion includes the returned index, it is the partition function's job to exclude the \"tail\" in non-advancing scenarios.** Which is to say, index j (the \"former\" index when indices cross) should be returned instead of i. Going with a similar logic, when considering the example of an already sorted array **[0, 1]**, the choice of pivot needs to be \"floor\" to ensure that the pointers stop on the \"former\" instead of the \"latter\" (with \"ceiling\" as the pivot, the index 1 would be returned and included in **(lo..p)** causing infinite recursion).\nIt is for the exact same reason why choice of the last element as pivot must be avoided.\nThe choice of recursing on (lo..p - 1) and (p..hi) follows the exact same logic as above.\n**Because the right half of the recursion includes the returned index, it is the partition function's job to exclude the \"head\" in non-advancing scenarios.** The index i (the \"latter\" index after the indices cross) in the partition function needs to be returned, and \"ceiling\" needs to be chosen as the pivot.\nThe two nuances are clear, again, when considering the examples of sorting an array where multiple identical elements exist (**[0, 0]**), and an already sorted array **[0, 1]** respectively.\nIt is noteworthy that with version of recursion, for the same reason, choice of the first element as pivot must be avoided.\n\n## Implementation issues\n\n### Choice of pivot\nIn the very early versions of quicksort, the leftmost element of the partition would often be chosen as the pivot element.\nUnfortunately, this causes worst-case behavior on already sorted arrays, which is a rather common use-case.\nThe problem was easily solved by choosing either a random index for the pivot, choosing the middle index of the partition or (especially for longer partitions) choosing the [median](https://bliptext.com/articles/median) of the first, middle and last element of the partition for the pivot (as recommended by [Sedgewick](https://bliptext.com/articles/robert-sedgewick-computer-scientist)).\nThis \"median-of-three\" rule counters the case of sorted (or reverse-sorted) input, and gives a better estimate of the optimal pivot (the true median) than selecting any single element, when no information about the ordering of the input is known.\nMedian-of-three code snippet for Lomuto partition:\nmid := ⌊(lo + hi) / 2⌋\n**if** A[mid] < A[lo]\nswap A[lo] with A[mid]\n**if** A[hi] < A[lo]\nswap A[lo] with A[hi]\n**if** A[mid] < A[hi]\nswap A[mid] with A[hi]\npivot := A[hi]\nIt puts a median into first, then that new value of is used for a pivot, as in a basic algorithm presented above.\nSpecifically, the expected number of comparisons needed to sort n elements (see ) with random pivot selection is\n1.386 n log n\n. Median-of-three pivoting brings this down to\nCn, 2 ≈ 1.188 n log n\n, at the expense of a three-percent increase in the expected number of swaps.\nAn even stronger pivoting rule, for larger arrays, is to pick the [ninther](https://bliptext.com/articles/ninther), a recursive median-of-three (Mo3), defined as\nSelecting a pivot element is also complicated by the existence of [integer overflow](https://bliptext.com/articles/integer-overflow).\nIf the boundary indices of the subarray being sorted are sufficiently large, the naïve expression for the middle index,\n(lo + hi)/2\n, will cause overflow and provide an invalid pivot index.\nThis can be overcome by using, for example,\nlo + (hi−lo)/2\nto index the middle element, at the cost of more complex arithmetic.\nSimilar issues arise in some other methods of selecting the pivot element.\n\n### Repeated elements\nWith a partitioning algorithm such as the Lomuto partition scheme described above (even one that chooses good pivot values), quicksort exhibits poor performance for inputs that contain many repeated elements.\nThe problem is clearly apparent when all the input elements are equal: at each recursion, the left partition is empty (no input values are less than the pivot), and the right partition has only decreased by one element (the pivot is removed).\nConsequently, the Lomuto partition scheme takes [quadratic time](https://bliptext.com/articles/quadratic-time) to sort an array of equal values.\nHowever, 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 (with memory cache reducing the swap overhead).\nIn 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.\nTo solve the Lomuto partition scheme problem (sometimes called the [Dutch national flag problem](https://bliptext.com/articles/dutch-national-flag-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.\n(Bentley and McIlroy call this a \"fat partition\" and it was already implemented in the qsort of [Version 7 Unix](https://bliptext.com/articles/version-7-unix). ) The values equal to the pivot are already sorted, so only the less-than and greater-than partitions need to be recursively sorted.\nIn pseudocode, the quicksort algorithm becomes:\n// Sorts (a portion of) an array, divides it into partitions, then sorts those\n**algorithm** quicksort(A, lo, hi) **is**\n**if** lo >= 0 && lo < hi **then**\nlt, gt := partition(A, lo, hi) // Multiple return values\nquicksort(A, lo, lt - 1)\nquicksort(A, gt + 1, hi)\n// Divides array into three partitions\n**algorithm** partition(A, lo, hi) **is**\n// Pivot value\npivot := A[(lo + hi) / 2] // Choose the middle element as the pivot (integer division)\n// Lesser, equal and greater index\nlt := lo eq := lo gt := hi // Iterate and compare all elements with the pivot\n**while** eq <= gt **do**\n**if** A[eq] < pivot **then**\n// Swap the elements at the equal and lesser indices\n**swap** A[eq] **with** A[lt]\n// Increase lesser index\nlt := lt + 1\n// Increase equal index\neq := eq + 1\n**else** **if** A[eq] > pivot **then**\n// Swap the elements at the equal and greater indices\n**swap** A[eq] **with** A[gt]\n// Decrease greater index\ngt := gt - 1\n**else** // **if** A[eq] = pivot **then**\n// Increase equal index\neq := eq + 1\n// Return lesser and greater indices\n**return** lt, gt\nThe algorithm returns indices to the first ('leftmost') and to the last ('rightmost') item of the middle partition.\nEvery other item of the partition is equal to the pivot and is therefore sorted.\nConsequently, the items of the partition need not be included in the recursive calls to.\nThe best case for the algorithm now occurs when all elements are equal (or are chosen from a small set of\nk ≪ n\nelements). 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 (assuming the subroutine takes no longer than linear time).\n\n### Optimizations\nOther important optimizations, also suggested by Sedgewick and widely used in practice, are:\nO(log n)\nspace is used, [recur](https://bliptext.com/articles/recurse) first into the smaller side of the partition, then use a [tail call](https://bliptext.com/articles/tail-call) to [recur](https://bliptext.com/articles/recurse) into the other, or update the parameters to no longer include the now sorted smaller side, and iterate to sort the larger side.\nO(kn)\ntime to finish the sort, which is linear if k is a constant.\nCompared to the \"many small sorts\" optimization, this version may execute fewer instructions, but it makes suboptimal use of the [cache memories](https://bliptext.com/articles/cache-memory) in modern computers.\n\n### Parallelization\nQuicksort's divide-and-conquer formulation makes it amenable to [parallelization](https://bliptext.com/articles/parallel-algorithm) using [task parallelism](https://bliptext.com/articles/task-parallelism).\nThe partitioning step is accomplished through the use of a [parallel prefix sum](https://bliptext.com/articles/prefix-sum) algorithm to compute an index for each array element in its section of the partitioned array.\nGiven an array of size n, the partitioning step performs\nO(n)\nwork in\nO(log n)\ntime and requires\nO(n)\nadditional scratch space.\nAfter the array has been partitioned, the two partitions can be sorted recursively in parallel.\nAssuming an ideal choice of pivots, parallel quicksort sorts an array of size n in\nO(n log n)\nwork in\nO(log2 n)\ntime using\nO(n)\nadditional space.\nQuicksort has some disadvantages when compared to alternative sorting algorithms, like [merge sort](https://bliptext.com/articles/merge-sort), which complicate its efficient parallelization.\nThe 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.\nAdditionally, it is difficult to parallelize the partitioning step efficiently in-place.\nThe use of scratch space simplifies the partitioning step, but increases the algorithm's memory footprint and constant overheads.\nOther more sophisticated parallel sorting algorithms can achieve even better time bounds.\nFor example, in 1991 [David M W Powers](https://bliptext.com/articles/david-m-w-powers) described a parallelized quicksort (and a related [radix sort](https://bliptext.com/articles/radix-sort)) that can operate in\nO(log n)\ntime on a [CRCW](https://bliptext.com/articles/parallel-random-access-machine) (concurrent read and concurrent write) [PRAM](https://bliptext.com/articles/parallel-random-access-machine) (parallel random-access machine) with n processors by performing partitioning implicitly.\n\n# Formal analysis\n\n## Worst-case analysis\nThe most unbalanced partition occurs when one of the sublists returned by the partitioning routine is of size\nn − 1\n. This may occur if the pivot happens to be the smallest or largest element in the list, or in some implementations (e.g., the Lomuto partition scheme as described above) when all the elements are equal.\nIf this happens repeatedly in every partition, then each recursive call processes a list of size one less than the previous list.\nConsequently, we can make\nn − 1\nnested calls before we reach a list of size 1.\nThis means that the [call tree](https://bliptext.com/articles/call-stack) is a linear chain of\nn − 1\nnested calls.\nThe ith call does\nO(n − i)\nwork to do the partition, and, so in that case quicksort takes\nO(n2)\ntime.\n\n## Best-case analysis\nIn the most balanced case, each time we perform a partition we divide the list into two nearly equal pieces.\nThis means each recursive call processes a list of half the size.\nConsequently, we can make only\nlog2 n\nnested calls before we reach a list of size 1.\nThis means that the depth of the [call tree](https://bliptext.com/articles/call-stack) is\nlog2 n\n. 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\nO(n)\ntime all together (each call has some constant overhead, but since there are only\nO(n)\ncalls at each level, this is subsumed in the\nO(n)\nfactor). The result is that the algorithm uses only\nO(n log n)\ntime.\n\n## Average-case analysis\nTo sort an array of n distinct elements, quicksort takes\nO(n log n)\ntime in expectation, averaged over all\nn!\npermutations of n elements with [equal probability](https://bliptext.com/articles/uniform-distribution-discrete).\nAlternatively, if the algorithm selects the pivot uniformly at random from the input array, the same analysis can be used to bound the expected running time for any input sequence; the expectation is then taken over the random choices made by the algorithm (Cormen et al., [Introduction to Algorithms](https://bliptext.com/articles/introduction-to-algorithms), Section 7.3).\nWe list here three common proofs to this claim providing different insights into quicksort's workings.\n\n### Using percentiles\nIf each pivot has rank somewhere in the middle 50 percent, that is, between the 25th [percentile](https://bliptext.com/articles/percentile) and the 75th [percentile](https://bliptext.com/articles/percentile), then it splits the elements with at least 25% and at most 75% on each side.\nIf 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\nO(n log n)\nalgorithm.\nWhen 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.\nHowever, 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.\nThat is good enough.\nImagine 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 k heads.\nAlthough this could take a long time, on average only\n2k\nflips are required, and the chance that the coin won't get k heads after\n100k\nflips is highly improbable (this can be made rigorous using [Chernoff bounds](https://bliptext.com/articles/chernoff-bound)).\nBy the same argument, Quicksort's recursion will terminate on average at a call depth of only.\nBut if its average call depth is\nO(log n)\n, and each level of the call tree processes at most n elements, the total amount of work done on average is the product,\nO(n log n)\n. 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.\n\n### Using recurrences\nAn alternative approach is to set up a [recurrence relation](https://bliptext.com/articles/recurrence-relation) for the\nT(n)\nfactor, the time needed to sort a list of size n. In the most unbalanced case, a single quicksort call involves\nO(n)\nwork plus two recursive calls on lists of size\n0\nand\nn−1\n, so the recurrence relation is\nThis is the same relation as for [insertion sort](https://bliptext.com/articles/insertion-sort) and [selection sort](https://bliptext.com/articles/selection-sort), and it solves to worst case\n.\nIn the most balanced case, a single quicksort call involves\nO(n)\nwork plus two recursive calls on lists of size\nn/2\n, so the recurrence relation is\nThe [master theorem for divide-and-conquer recurrences](https://bliptext.com/articles/master-theorem-analysis-of-algorithms) tells us that\n.\nThe outline of a formal proof of the\nO(n log n)\nexpected time complexity follows.\nAssume that there are no duplicates as duplicates could be handled with linear time pre- and post-processing, or considered cases easier than the analyzed.\nWhen the input is a random permutation, the rank of the pivot is uniform random from 0 to\nn − 1\n. Then the resulting parts of the partition have sizes i and\nn − i − 1\n, and i is uniform random from 0 to\nn − 1\n. So, averaging over all possible splits and noting that the number of comparisons for the partition is\nn − 1\n, the average number of comparisons over all permutations of the input sequence can be estimated accurately by solving the recurrence relation:\nSolving the recurrence gives\n.\nThis means that, on average, quicksort performs only about 39% worse than in its best case.\nIn this sense, it is closer to the best case than the worst case.\nA [comparison sort](https://bliptext.com/articles/comparison-sort) cannot use less than\nlog2(n!)\ncomparisons on average to sort n items (as [explained in the article Comparison sort](https://bliptext.com/articles/comparison-sort)) and in case of large n, [Stirling's approximation](https://bliptext.com/articles/stirling-s-approximation) yields\nlog2(n!) ≈ n(log2 n − log2 e)\n, so quicksort is not much worse than an ideal comparison sort.\nThis fast average runtime is another reason for quicksort's practical dominance over other sorting algorithms.\n\n### Using a binary search tree\nThe following [binary search tree](https://bliptext.com/articles/binary-search-tree) (BST) corresponds to each execution of quicksort: 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.\nThe number of comparisons of the execution of quicksort equals the number of comparisons during the construction of the BST by a sequence of insertions.\nSo, the average number of comparisons for randomized quicksort equals the average cost of constructing a BST when the values inserted form a random permutation.\nConsider a BST created by insertion of a sequence of values forming a random permutation.\nLet C denote the cost of creation of the BST.\nWe have, where c_{i,j} is a binary random variable expressing whether during the insertion of x_i there was a comparison to x_j.\nBy [linearity of expectation](https://bliptext.com/articles/expected-value), the expected value of C is.\nFix i and\nj= hi || lo = 0 && hi >= 0 && lo pivot\n// If the indices crossed, return\n**if** i >= j **then** **return** j // Swap the elements at the left and right indices\n**swap** A[i] **with** A[j]\nThe entire array is sorted by quicksort(A, 0, length(A) - 1).\nHoare's scheme is more efficient than Lomuto's partition scheme because it does three times fewer swaps on average.\nAlso, as mentioned, the implementation given creates a balanced partition even when all values are equal.\n, which Lomuto's scheme does not.\nLike Lomuto's partition scheme, Hoare's partitioning also would cause Quicksort to degrade to\nO(n2)\nfor already sorted input, if the pivot was chosen as the first or the last element.\nWith the middle element as the pivot, however, sorted data results with (almost) no swaps in equally sized partitions leading to best case behavior of Quicksort, i.e.\nO(n log(n))\n. Like others, Hoare's partitioning doesn't produce a stable sort.\nIn 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.\nTherefore, the next two segments that the main algorithm recurs on are (lo..p) (elements ≤ pivot) and (p+1..hi) (elements ≥ pivot) as opposed to (lo..p-1) and (p+1..hi) as in Lomuto's scheme.\n**Subsequent recursions (expansion on previous paragraph)**\nLet's expand a little bit on the next two segments that the main algorithm recurs on.\nBecause we are using strict comparators (>, = 0 && lo pivot **then**\n// Swap the elements at the equal and greater indices\n**swap** A[eq] **with** A[gt]\n// Decrease greater index\ngt := gt - 1\n**else** // **if** A[eq] = pivot **then**\n// Increase equal index\neq := eq + 1\n// Return lesser and greater indices\n**return** lt, gt\nThe algorithm returns indices to the first ('leftmost') and to the last ('rightmost') item of the middle partition.\nEvery other item of the partition is equal to the pivot and is therefore sorted.\nConsequently, the items of the partition need not be included in the recursive calls to.\nThe best case for the algorithm now occurs when all elements are equal (or are chosen from a small set of\nk ≪ n\nelements). 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 (assuming the subroutine takes no longer than linear time).\n\n### Optimizations\nOther important optimizations, also suggested by Sedgewick and widely used in practice, are:\nO(log n)\nspace is used, [recur](https://bliptext.com/articles/recurse) first into the smaller side of the partition, then use a [tail call](https://bliptext.com/articles/tail-call) to [recur](https://bliptext.com/articles/recurse) into the other, or update the parameters to no longer include the now sorted smaller side, and iterate to sort the larger side.\nO(kn)\ntime to finish the sort, which is linear if k is a constant.\nCompared to the \"many small sorts\" optimization, this version may execute fewer instructions, but it makes suboptimal use of the [cache memories](https://bliptext.com/articles/cache-memory) in modern computers.\n\n### Parallelization\nQuicksort's divide-and-conquer formulation makes it amenable to [parallelization](https://bliptext.com/articles/parallel-algorithm) using [task parallelism](https://bliptext.com/articles/task-parallelism).\nThe partitioning step is accomplished through the use of a [parallel prefix sum](https://bliptext.com/articles/prefix-sum) algorithm to compute an index for each array element in its section of the partitioned array.\nGiven an array of size n, the partitioning step performs\nO(n)\nwork in\nO(log n)\ntime and requires\nO(n)\nadditional scratch space.\nAfter the array has been partitioned, the two partitions can be sorted recursively in parallel.\nAssuming an ideal choice of pivots, parallel quicksort sorts an array of size n in\nO(n log n)\nwork in\nO(log2 n)\ntime using\nO(n)\nadditional space.\nQuicksort has some disadvantages when compared to alternative sorting algorithms, like [merge sort](https://bliptext.com/articles/merge-sort), which complicate its efficient parallelization.\nThe 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.\nAdditionally, it is difficult to parallelize the partitioning step efficiently in-place.\nThe use of scratch space simplifies the partitioning step, but increases the algorithm's memory footprint and constant overheads.\nOther more sophisticated parallel sorting algorithms can achieve even better time bounds.\nFor example, in 1991 [David M W Powers](https://bliptext.com/articles/david-m-w-powers) described a parallelized quicksort (and a related [radix sort](https://bliptext.com/articles/radix-sort)) that can operate in\nO(log n)\ntime on a [CRCW](https://bliptext.com/articles/parallel-random-access-machine) (concurrent read and concurrent write) [PRAM](https://bliptext.com/articles/parallel-random-access-machine) (parallel random-access machine) with n processors by performing partitioning implicitly.\n\n# Formal analysis\n\n## Worst-case analysis\nThe most unbalanced partition occurs when one of the sublists returned by the partitioning routine is of size\nn − 1\n. This may occur if the pivot happens to be the smallest or largest element in the list, or in some implementations (e.g., the Lomuto partition scheme as described above) when all the elements are equal.\nIf this happens repeatedly in every partition, then each recursive call processes a list of size one less than the previous list.\nConsequently, we can make\nn − 1\nnested calls before we reach a list of size 1.\nThis means that the [call tree](https://bliptext.com/articles/call-stack) is a linear chain of\nn − 1\nnested calls.\nThe ith call does\nO(n − i)\nwork to do the partition, and, so in that case quicksort takes\nO(n2)\ntime.\n\n## Best-case analysis\nIn the most balanced case, each time we perform a partition we divide the list into two nearly equal pieces.\nThis means each recursive call processes a list of half the size.\nConsequently, we can make only\nlog2 n\nnested calls before we reach a list of size 1.\nThis means that the depth of the [call tree](https://bliptext.com/articles/call-stack) is\nlog2 n\n. 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\nO(n)\ntime all together (each call has some constant overhead, but since there are only\nO(n)\ncalls at each level, this is subsumed in the\nO(n)\nfactor). The result is that the algorithm uses only\nO(n log n)\ntime.\n\n## Average-case analysis\nTo sort an array of n distinct elements, quicksort takes\nO(n log n)\ntime in expectation, averaged over all\nn!\npermutations of n elements with [equal probability](https://bliptext.com/articles/uniform-distribution-discrete).\nAlternatively, if the algorithm selects the pivot uniformly at random from the input array, the same analysis can be used to bound the expected running time for any input sequence; the expectation is then taken over the random choices made by the algorithm (Cormen et al., [Introduction to Algorithms](https://bliptext.com/articles/introduction-to-algorithms), Section 7.3).\nWe list here three common proofs to this claim providing different insights into quicksort's workings.\n\n### Using percentiles\nIf each pivot has rank somewhere in the middle 50 percent, that is, between the 25th [percentile](https://bliptext.com/articles/percentile) and the 75th [percentile](https://bliptext.com/articles/percentile), then it splits the elements with at least 25% and at most 75% on each side.\nIf 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\nO(n log n)\nalgorithm.\nWhen 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.\nHowever, 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.\nThat is good enough.\nImagine 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 k heads.\nAlthough this could take a long time, on average only\n2k\nflips are required, and the chance that the coin won't get k heads after\n100k\nflips is highly improbable (this can be made rigorous using [Chernoff bounds](https://bliptext.com/articles/chernoff-bound)).\nBy the same argument, Quicksort's recursion will terminate on average at a call depth of only.\nBut if its average call depth is\nO(log n)\n, and each level of the call tree processes at most n elements, the total amount of work done on average is the product,\nO(n log n)\n. 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.\n\n### Using recurrences\nAn alternative approach is to set up a [recurrence relation](https://bliptext.com/articles/recurrence-relation) for the\nT(n)\nfactor, the time needed to sort a list of size n. In the most unbalanced case, a single quicksort call involves\nO(n)\nwork plus two recursive calls on lists of size\n0\nand\nn−1\n, so the recurrence relation is\nThis is the same relation as for [insertion sort](https://bliptext.com/articles/insertion-sort) and [selection sort](https://bliptext.com/articles/selection-sort), and it solves to worst case\n.\nIn the most balanced case, a single quicksort call involves\nO(n)\nwork plus two recursive calls on lists of size\nn/2\n, so the recurrence relation is\nThe [master theorem for divide-and-conquer recurrences](https://bliptext.com/articles/master-theorem-analysis-of-algorithms) tells us that\n.\nThe outline of a formal proof of the\nO(n log n)\nexpected time complexity follows.\nAssume that there are no duplicates as duplicates could be handled with linear time pre- and post-processing, or considered cases easier than the analyzed.\nWhen the input is a random permutation, the rank of the pivot is uniform random from 0 to\nn − 1\n. Then the resulting parts of the partition have sizes i and\nn − i − 1\n, and i is uniform random from 0 to\nn − 1\n. So, averaging over all possible splits and noting that the number of comparisons for the partition is\nn − 1\n, the average number of comparisons over all permutations of the input sequence can be estimated accurately by solving the recurrence relation:\nSolving the recurrence gives\n.\nThis means that, on average, quicksort performs only about 39% worse than in its best case.\nIn this sense, it is closer to the best case than the worst case.\nA [comparison sort](https://bliptext.com/articles/comparison-sort) cannot use less than\nlog2(n!)\ncomparisons on average to sort n items (as [explained in the article Comparison sort](https://bliptext.com/articles/comparison-sort)) and in case of large n, [Stirling's approximation](https://bliptext.com/articles/stirling-s-approximation) yields\nlog2(n!) ≈ n(log2 n − log2 e)\n, so quicksort is not much worse than an ideal comparison sort.\nThis fast average runtime is another reason for quicksort's practical dominance over other sorting algorithms.\n\n### Using a binary search tree\nThe following [binary search tree](https://bliptext.com/articles/binary-search-tree) (BST) corresponds to each execution of quicksort: 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.\nThe number of comparisons of the execution of quicksort equals the number of comparisons during the construction of the BST by a sequence of insertions.\nSo, the average number of comparisons for randomized quicksort equals the average cost of constructing a BST when the values inserted form a random permutation.\nConsider a BST created by insertion of a sequence of values forming a random permutation.\nLet C denote the cost of creation of the BST.\nWe have, where c_{i,j} is a binary random variable expressing whether during the insertion of x_i there was a comparison to x_j.\nBy [linearity of expectation](https://bliptext.com/articles/expected-value), the expected value of C is.\nFix i and\nj