933:
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. (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. Such 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).
908:
first pointer is still before the second, these elements are in the wrong order relative to each other, and they are then exchanged. After 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). With this formulation it is possible that one sub-range turns out to be the whole original range, which would prevent the algorithm from advancing. Hoare 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.
3729:
3179:
5312:) 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
5809:, 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. Once 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
651:
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. Due 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. The steps for
3840:(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. 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
3724:{\displaystyle {\begin{aligned}{\frac {C(n)}{n+1}}&={\frac {C(n-1)}{n}}+{\frac {2}{n+1}}-{\frac {2}{n(n+1)}}\leq {\frac {C(n-1)}{n}}+{\frac {2}{n+1}}\\&={\frac {C(n-2)}{n-1}}+{\frac {2}{n}}-{\frac {2}{(n-1)n}}+{\frac {2}{n+1}}\leq {\frac {C(n-2)}{n-1}}+{\frac {2}{n}}+{\frac {2}{n+1}}\\&\ \ \vdots \\&={\frac {C(1)}{2}}+\sum _{i=2}^{n}{\frac {2}{i+1}}\leq 2\sum _{i=1}^{n-1}{\frac {1}{i}}\approx 2\int _{1}^{n}{\frac {1}{x}}\mathrm {d} x=2\ln n\end{aligned}}}
6404:
622:
1079:. 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. Therefore, the next two segments that the main algorithm recurs on are
1772:, 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.
6170:), and two arrays are filled with the positions of elements to swap. (To avoid conditional branches, the position is unconditionally stored at the end of the array, and the index of the end is incremented if a swap is needed.) 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.
1119:, 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. With this example, we see how it is necessary to include the returned index of the partition function in our subsequent recursions. As a result, we are presented with the choices of either recursing on
29:
588:. 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
732:(inclusive) 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. The complexity of Quicksort with this scheme degrades to
5043:
additional space for the management of explicit or implicit recursion). For variant quicksorts involving extra memory due to representations using pointers (e.g. lists or trees) or files (effectively lists), it is trivial to maintain stability. The more complex, or disk-bound, data structures tend to
2161:
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.
1432:
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
907:
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
674:
instance of the pivot is present, most partition routines ensure that the value that ends up at the point of division is equal to the pivot, and is now in its final position (but termination of quicksort does not depend on this, as long as sub-ranges strictly smaller than the original are produced).
5947:
and quicksort. Pick an element from the array (the pivot) and consider the first character (key) of the string (multikey). 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
1427:
With 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. The problem is clearly apparent when all the input elements are equal: at each recursion,
1228:
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
932:
which is actually reflected by the use of strict comparison operators). While 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. Indeed, since at least one
685:
The 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. In discussing the efficiency of quicksort, it is therefore necessary to specify these choices
650:
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
680:
apply the quicksort to the sub-range up to the point of division and to the sub-range after it, possibly excluding from both ranges the element equal to the pivot at the point of division. (If the partition produces a possibly larger sub-range near the boundary where all elements are known to be
641:
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
5031:
is stability – that is the order of elements that compare equal is not changed, allowing controlling order of multikey tables (e.g. directory or folder listings) in a natural way. This property is hard to maintain for in-place quicksort (that uses only constant additional space for pointers and
1051:
Hoare's scheme is more efficient than Lomuto's partition scheme because it does three times fewer swaps on average. Also, as mentioned, the implementation given creates a balanced partition even when all values are equal., which Lomuto's scheme does not. Like Lomuto's partition scheme, Hoare's
911:
With respect to this original description, implementations often make minor but important variations. Notably, 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
673:
the range: reorder its elements, while determining a point of division, so that all elements with values less than the pivot come before the division, while all elements with values greater than the pivot come after it; elements that are equal to the pivot can go either way. Since at least one
1440:), 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. (Bentley and McIlroy call this a "fat partition" and it was already implemented in the
1587:
algorithm returns indices to the first ('leftmost') and to the last ('rightmost') item of the middle partition. Every other item of the partition is equal to the pivot and is therefore sorted. Consequently, the items of the partition need not be included in the recursive calls to
2609:
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
1208:
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. The two nuances are clear, again, when considering the examples of sorting an array where multiple identical elements exist
2077:. Alternatively, 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
5014:
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.
5027:. 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
4831:
743:
when the array is already in order, due to the partition being the worst possible one. There 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
625:
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
2837:
5760:
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
1063:
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 (almost) no swaps in equally sized partitions leading to best case behavior of
Quicksort, i.e.
1237:). This "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.
1433:
elements increases (with memory cache reducing the swap overhead). 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.
5156:
be implemented as a stable sort using linked lists, there is no reason to; it will often suffer from poor pivot choices without random access, and is essentially always inferior to merge sort. Merge sort is also the algorithm of choice for
4903:
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
6153:
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
5196:. 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
338:. 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. For this reason, it is sometimes called
5328:). 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.
5280:
running time. Practical implementations of 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.
5336:
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
4256:
2162:
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
579:
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
1962:
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
5191:
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
1826:. 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.
659:
If the range has fewer than two elements, return immediately as there is nothing to do. Possibly for other very short lengths a special-purpose sorting method is applied and the remainder of these steps
5089:
is a variant of quicksort which solves this problem by switching to heapsort when a bad case is detected. Major programming languages, such as C++ (in the GNU and LLVM implementations), use introsort.
3085:
1428:
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). Consequently, the Lomuto partition scheme takes
1733:
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
2559:
1941:
3184:
2936:
2431:
4595:
5074:. This result is debatable; some publications indicate the opposite. The main disadvantage of quicksort is the implementation complexity required to avoid bad pivot choices and the resultant
4040:
2102:
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
1187:, 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
5175:
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.
6210:
and David C. Kandathil, in 2004, discovered a one-parameter family of sorting algorithms, called partition sorts, which on average (with all input orderings equally likely) perform at most
6112:
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
4695:
4517:
4334:
3971:
3903:
5871:
5116:
and has excellent worst-case performance. The main disadvantage of merge sort is that it is an out-of-place algorithm, so when operating on arrays, efficient implementations require
884:
7237:
elements), depending on whether the pivot is included in one of subpartitions, as in the Hoare's partitioning routine, or is excluded from both of them, like in the Lomuto's routine.
1450:.) 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:
1184:
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
6341:
3171:
2652:
563:'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
495:. As a part of the translation process, he needed to sort the words in Russian sentences before looking them up in a Russian-English dictionary, which was in alphabetical order on
5225:
algorithm, chooses pivots more carefully, ensuring that the pivots are near the middle of the data (between the 30th and 70th percentiles), and thus has guaranteed linear time –
1165:. If index i (the "latter" index) is returned after indices cross in the partition function, the index 1 would be returned after the first partition. The subsequent recursion on
6294:
4166:
5948:
than" and "greater than" partitions on the same character. Recursively sort the "equal to" partition by the next character (key). Given we sort using bytes or words of length
4684:
3828:, 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.
5807:
6254:
2230:
2141:
1605:
elements). 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
425:
7130:
Although saving small subarrays until the end makes sense from an instruction count perspective, it is exactly the wrong thing to do from a cache performance perspective.
6378:
2262:. 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.
220:
139:
296:
5927:
469:
90:
4073:
5418:
1647:
that performs fewer swaps, comparisons or other operations on such small arrays. The ideal 'threshold' will vary based on the details of the specific implementation.
4649:
4622:
4449:
4422:
4395:
4368:
4127:
4100:
1109:
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. Therefore,
260:
170:
6000:
algorithms including quicksort. This is a kind of three-way quicksort in which the middle partition represents a (trivially) sorted subarray of elements that are
373:
are only swapped in case their relative order has been obtained in the transitive closure of prior comparison-outcomes. Most implementations of quicksort are not
5381:
5358:
5891:
5758:
5738:
5718:
5698:
5678:
5658:
5638:
5618:
5598:
5578:
5558:
5538:
5518:
5498:
5478:
5458:
5438:
3766:
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
8041:
7285:= 2) and on larger instances it suffers from its poor cache behavior (in our experiments more than eight times slower than Quicksort for sorting 2 elements).
1829:
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
1182:, 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.
575:
in 1993 incorporated various improvements for use in programming libraries, including a technique to deal with equal elements and a pivot scheme known as
1206:
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.
6134:
behaviours of standard quicksort and radix quicksort, and will be faster even in the best case of those comparison algorithms under these conditions of
1776:
895:
respectively), the black outlines show the positions of the sorted elements, and the filled black square shows the value that is being compared to (
6437:
613:) function in 1998, which consistently drives even his 1993 variant of Quicksort into quadratic behavior by producing adversarial data on-the-fly.
1103:
Let's expand a little bit on the next two segments that the main algorithm recurs on. Because we are using strict comparators (>, <) in the
2646:, the average number of comparisons over all permutations of the input sequence can be estimated accurately by solving the recurrence relation:
1677:
is a constant. Compared to the "many small sorts" optimization, this version may execute fewer instructions, but it makes suboptimal use of the
1419:
to index the middle element, at the cost of more complex arithmetic. Similar issues arise in some other methods of selecting the pivot element.
1310:, 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
5265:
selection algorithm, one can use it to find the ideal pivot (the median) at every step of quicksort and thus produce a sorting algorithm with
585:
5294:
Instead of partitioning into two subarrays using a single pivot, multi-pivot quicksort (also multiquicksort) partitions its input into some
4175:
887:
An animated demonstration of
Quicksort using Hoare's partition scheme. The red outlines show the positions of the left and right pointers (
7387:
1654:, simply stop; then after the whole array has been processed, perform insertion sort on it. Stopping the recursion early leaves the array
1215:
respectively. It is noteworthy that with version of recursion, for the same reason, choice of the first element as pivot must be avoided.
7839:
6789:
4985:
bits of space. This space requirement isn't too terrible, though, since if the list contained distinct elements, it would need at least
1640:
to recur into the other, or update the parameters to no longer include the now sorted smaller side, and iterate to sort the larger side.
1987:. 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
8050:
7517:
1795:
5660:
buffer is read from the file. The process continues until all segments are read and one write buffer remains. If that buffer is an
3787:
7317:
2944:
2565:
8022:
1643:
When the number of elements is below some threshold (perhaps ten elements), switch to a non-recursive sorting algorithm such as
8558:
2490:
1869:
7660:
7428:
7335:
7274:
7189:
7049:
7001:
6987:
6960:
6723:
6586:
6512:
6381:
4885:
1234:
560:
7588:
8001:
1392:. If the boundary indices of the subarray being sorted are sufficiently large, the naïve expression for the middle index,
6177:'s C++ STL implementation, libcxx, providing a 50% improvement on random integer sequences. Pattern-defeating quicksort (
2843:
667:, that occurs in the range (the precise manner of choosing depends on the partition routine, and can involve randomness).
534:
Communications of the ACM (CACM), Volume 4, Issue 7 July 1961, pp 321 Algorithm 63: partition and
Algorithm 64: Quicksort
2317:
960:
p := partition(A, lo, hi) quicksort(A, lo, p) // Note: the pivot is now included quicksort(A, p + 1, hi)
4522:
515:
that he did not. His boss ultimately accepted that he had lost the bet. Hoare published a paper about his algorithm in
7444:
3980:
1193:
causing infinite recursion). It is for the exact same reason why choice of the last element as pivot must be avoided.
323:
in 1959 and published in 1961. It is still a commonly used algorithm for sorting. Overall, it is slightly faster than
8084:
7902:
7862:
6862:
6158:, limiting performance. BlockQuicksort rearranges the computations of quicksort to convert unpredictable branches to
1702:
algorithm to compute an index for each array element in its section of the partitioned array. Given an array of size
1143:) we return in the partition function when the indices cross, and how we choose our pivot in the partition function (
708:. In most formulations this scheme chooses as the pivot the last element in the array. The algorithm maintains index
7142:
4826:{\displaystyle \operatorname {E} =\sum _{i}\sum _{j<i}{\frac {2}{j+1}}=O\left(\sum _{i}\log i\right)=O(n\log n).}
7619:
Edelkamp, Stefan; Weiß, Armin (22 April 2016). "BlockQuicksort: How Branch
Mispredictions don't affect Quicksort".
6711:
6385:
6380:
space. Practical efficiency and smaller variance in performance were demonstrated against optimised quicksorts (of
568:
492:
8107:
6031:
and quicksort but the quicksort left/right partition decision is made on successive bits of the key, and is thus
4457:
4278:
3911:
3843:
2074:
507:
but had trouble dealing with the list of unsorted segments. On return to
England, he was asked to write code for
7281:
on small instances
Heapsort is already considerably slower than Quicksort (in our experiments more than 30% for
7160:
5812:
8415:
6536:
6024:
4926:
space. However, without
Sedgewick's trick to limit the recursive calls, in the worst case quicksort could make
2832:{\displaystyle C(n)=n-1+{\frac {1}{n}}\sum _{i=0}^{n-1}(C(i)+C(n-i-1))=n-1+{\frac {2}{n}}\sum _{i=0}^{n-1}C(i)}
1799:
1775:
Other more sophisticated parallel sorting algorithms can achieve even better time bounds. For example, in 1991
5420:
the number of buffer segments in the file. Data is read (and written) from both ends of the file inwards. Let
5236:. This same pivot strategy can be used to construct a variant of quicksort (median of medians quicksort) with
1819:
The most unbalanced partition occurs when one of the sublists returned by the partitioning routine is of size
5251:
time. However, the overhead of choosing the pivot is significant, so this is generally not used in practice.
526:
and its ability to do recursion that enabled him to publish an improved version of the algorithm in ALGOL in
6299:
4869:
After partitioning, the partition with the fewest elements is (recursively) sorted first, requiring at most
3093:
594:
although it is inferior to Hoare's scheme because it does three times more swaps on average and degrades to
677:
647:
432:
384:
343:
335:
226:
177:
96:
49:
1595:
The best case for the algorithm now occurs when all elements are equal (or are chosen from a small set of
8448:
6409:
4974:
items. Because there are such variables in every stack frame, quicksort using
Sedgewick's trick requires
3795:
1437:
1229:
the pivot, choosing the middle index of the partition or (especially for longer partitions) choosing the
554:
6259:
4139:
2639:. So, averaging over all possible splits and noting that the number of comparisons for the partition is
567:, adaptive partitioning by Van Emden as well as derivation of expected number of comparisons and swaps.
8548:
7885:
7574:
6852:
6145:. See Powers for further discussion of the hidden overheads in comparison, radix and parallel sorting.
2090:
We list here three common proofs to this claim providing different insights into quicksort's workings.
2083:
704:
590:
496:
8246:
7094:
LaMarca, Anthony; Ladner, Richard E. (1999). "The
Influence of Caches on the Performance of Sorting".
6441:
4654:
1650:
An older variant of the previous optimization: when the number of elements is less than the threshold
1404:, will cause overflow and provide an invalid pivot index. This can be overcome by using, for example,
1172:. A non-advancing separation that causes infinite recursion is produced. It is therefore obvious that
8553:
8122:
7925:
7760:
7726:
7665:
7054:
6551:
6471:
5764:
5321:
5313:
528:
7034:
6213:
519:
8420:
7969:
7938:
7215:
7108:
6631:
5166:
4884:
or iteration, which doesn't add to the call stack. This idea, as discussed above, was described by
2191:
7540:
Motzkin, D.; Hansen, C.L. (1982), "An efficient external sorting with minimal space requirement",
2105:
390:
6614:
6346:
2188:). By the same argument, Quicksort's recursion will terminate on average at a call depth of only
512:
484:
187:
106:
8328:
8208:
8162:
8132:
7964:
7933:
7394:
7210:
7103:
6879:
6626:
6054:
380:
374:
266:
7912:
5896:
5070:
running time is usually considered slower than in-place quicksort, primarily due to its worse
438:
59:
8489:
8077:
5071:
4045:
1617:
Other important optimizations, also suggested by
Sedgewick and widely used in practice, are:
7923:
Martínez, C.; Roura, S. (2001). "Optimal Sampling Strategies in Quicksort and Quickselect".
5386:
8468:
8333:
8188:
7872:
7790:
7368:
7021:
6840:
6155:
4855:, even in the worst case, when it is carefully implemented using the following strategies.
4627:
4600:
4427:
4400:
4373:
4346:
4105:
4078:
1290:
516:
361:, meaning that it can sort items of any type for which a "less-than" relation (formally, a
7810:
7313:
7024:
236:
146:
8:
8484:
8223:
7516:
Kushagra, Shrinu; López-Ortiz, Alejandro; Munro, J. Ian; Qiao, Aurick (7 February 2014).
5938:
5317:
5184:
4133:
2271:
1111:
the index returned in the partition function isn't necessarily where the actual pivot is.
488:
33:
Animated visualization of the quicksort algorithm. The horizontal lines are pivot values.
7696:"A simple expected running time analysis for randomized 'divide and conquer' algorithms"
7372:
5363:
5340:
1233:
of the first, middle and last element of the partition for the pivot (as recommended by
8374:
8349:
8323:
8127:
7982:
7916:
7743:
7682:
7620:
7557:
7471:
7358:
7252:
7121:
7071:
6966:
6793:
6693:
6644:
6568:
5876:
5743:
5723:
5703:
5683:
5663:
5643:
5623:
5603:
5583:
5563:
5543:
5523:
5503:
5483:
5463:
5443:
5423:
3837:
1768:
Quicksort has some disadvantages when compared to alternative sorting algorithms, like
1691:
652:
544:
347:
8193:
8093:
8026:
7898:
7858:
7643:, European Symposium on Algorithms, 14–17 September 2004, Bergen, Norway. Published:
7526:
7424:
7270:
7185:
7125:
6997:
6956:
6921:
6858:
6719:
6714:(2007). "The most beautiful code I never wrote". In Oram, Andy; Wilson, Greg (eds.).
6685:
6532:
6508:
6159:
5580:
write buffer in descending order based comparison with the pivot record. Once either
5222:
5028:
2098:
If each pivot has rank somewhere in the middle 50 percent, that is, between the 25th
316:
42:
8261:
7747:
7686:
7075:
6797:
5152:, requiring only a small, constant amount of auxiliary storage. Although quicksort
511:. Hoare mentioned to his boss that he knew of a faster algorithm and his boss bet a
503:, would be slow, he came up with a new idea. He wrote the partition part in Mercury
8435:
8302:
8070:
7986:
7974:
7943:
7876:
7868:
7835:
7798:
7769:
7735:
7707:
7674:
7601:
7561:
7549:
7496:
7416:
7262:
7113:
7063:
6970:
6948:
6911:
6836:
6785:
6697:
6675:
6648:
6636:
6572:
6560:
6480:
5158:
5024:
1695:
1389:
533:
532:, the premier computer science journal of the time. The ALGOL code is published in
229:
7640:
7251:. ALENEX 2019: 21st Workshop on Algorithm Engineering and Experiments. San Diego.
1998:
time all together (each call has some constant overhead, but since there are only
1662:
positions away from its final sorted position. In this case, insertion sort takes
8496:
8379:
8251:
8152:
8147:
8137:
7179:
6991:
6945:
Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data
6940:
6502:
6389:
6343:
comparisons (and also operations); these are in-place, requiring only additional
6207:
6190:
6088:
6050:
5997:
3767:
572:
358:
180:
99:
52:
7823:
7577:, Australasian Computer Architecture Workshop, Flinders University, January 1995
6770:
5044:
increase time cost, in general making increasing use of virtual memory or disk.
1973:
nested calls before we reach a list of size 1. This means that the depth of the
694:
This scheme is attributed to Nico Lomuto and popularized by Bentley in his book
8501:
8410:
8277:
8231:
8157:
8112:
8005:
7880:
7415:. Proceedings. Society for Industrial and Applied Mathematics. pp. 55–69.
7298:
6848:
4881:
2441:
2437:
2185:
1644:
1447:
1429:
1162:, with the example of sorting an array where multiple identical elements exist
745:
500:
7947:
7712:
7695:
7501:
7491:
Kushagra, Shrinu; López-Ortiz, Alejandro; Qiao, Aurick; Munro, J. Ian (2014).
7420:
7266:
1454:// Sorts a (portion of an) array, divides it into partitions, then sorts those
944:// Sorts a (portion of an) array, divides it into partitions, then sorts those
768:// Sorts a (portion of an) array, divides it into partitions, then sorts those
8542:
8369:
8142:
8056:
6993:
Algorithms in C: Fundamentals, Data Structures, Sorting, Searching, Parts 1–4
6925:
6689:
6498:
6178:
6163:
7803:
7785:
6952:
6916:
6899:
6790:
10.1002/(SICI)1097-024X(19990410)29:4<341::AID-SPE237>3.0.CO;2-R
6564:
5460:
represent segments that start at the end of the file. Data is read into the
8384:
8297:
8167:
7978:
7908:
7846:
7819:
7141:
Umut A. Acar, Guy E Blelloch, Margaret Reid-Miller, and Kanat Tangwongsan,
7117:
6640:
5207:
time, which is optimal for selection, but the selection algorithm is still
5162:
1678:
7840:
10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-#
7773:
7739:
7678:
7067:
6680:
6663:
6484:
5051:. Heapsort has the advantages of simplicity, and a worst case run time of
1633:
1004:// Move the right index to the left at least once and while the element at
990:// Move the left index to the right at least once and while the element at
8517:
8359:
8183:
8117:
7894:
5193:
5172:
5149:
5113:
843:// Swap the current element with the element at the temporary pivot index
362:
351:
28:
7605:
7470:
Wild, Sebastian (3 November 2015). "Why Is Dual-Pivot Quicksort Fast?".
6587:"My Quickshort interview with Sir Tony Hoare, the inventor of Quicksort"
912:"greater than" and "less than" respectively; since the formulation uses
377:, meaning that the relative order of equal sort items is not preserved.
8463:
8443:
8425:
8389:
8318:
8256:
8241:
8203:
7781:
7755:
7721:
7553:
6895:
6844:
6744:
6466:
6167:
6123:
relatively useless bits but quick radix sort will avoid the worst case
6028:
5944:
5094:
4075:
is a binary random variable expressing whether during the insertion of
2099:
1974:
1837:
1780:
1769:
1699:
937:
904:
749:
564:
543:
as the default library sort subroutine. Hence, it lent its name to the
480:
324:
320:
7955:
Bentley, J. L.; McIlroy, M. D. (1993). "Engineering a sort function".
4251:{\displaystyle \operatorname {E} =\sum _{i}\sum _{j<i}\Pr(c_{i,j})}
605:
runtime when all elements are equal. McIlroy would further produce an
8458:
8394:
8364:
8354:
8292:
8287:
8282:
8198:
8062:
8045:
7890:
6417:
5086:
1637:
508:
7495:. Proc. Workshop on Algorithm Engineering and Experiments (ALENEX).
6403:
1116:, following the scheme, after the first partition the array becomes
883:
621:
8527:
8522:
8236:
7625:
7476:
7257:
7017:
5440:
represent the segments that start at the beginning of the file and
5048:
2247:
elements, the total amount of work done on average is the product,
1836:
nested calls before we reach a list of size 1. This means that the
1436:
To solve the Lomuto partition scheme problem (sometimes called the
504:
328:
7363:
5112:
sorting algorithm. Merge sort's main advantages are that it is a
1388:
Selecting a pivot element is also complicated by the existence of
8453:
7035:
http://www.ugrad.cs.ubc.ca/~cs260/chnotes/ch6/Ch6CovCompiled.html
6549:
Shustek, L. (2009). "Interview: An interview with C.A.R. Hoare".
6256:
comparisons (close to the information theoretic lower bound) and
5325:
1311:
539:
Quicksort gained widespread adoption, appearing, for example, in
7915:. CS 332: Designing Algorithms. Department of Computer Science,
5138:
for quicksort with in-place partitioning and tail recursion, or
4859:
In-place partitioning is used. This unstable partition requires
2289:. In the most unbalanced case, a single quicksort call involves
1690:
Quicksort's divide-and-conquer formulation makes it amenable to
1269:
Specifically, the expected number of comparisons needed to sort
7597:
6162:. When partitioning, the input is divided into moderate-sized
5161:
of very large data sets stored on slow-to-access media such as
1230:
7411:
Wild, S.; Nebel, M.; Reitzig, R.; Laube, U. (7 January 2013).
5500:
read buffers. A pivot record is chosen and the records in the
5003:
Another, less common, not-in-place, version of quicksort uses
1266:
is used for a pivot, as in a basic algorithm presented above.
1169:
would be on (0, 1), which corresponds to the exact same array
6857:(3rd ed.). MIT Press and McGraw-Hill. pp. 170–190.
6181:), a version of introsort, also incorporates this technique.
2166:
heads. Although this could take a long time, on average only
1698:. The partitioning step is accomplished through the use of a
1442:
1135:. Which of the two options we choose depends on which index (
549:
523:
7515:
7490:
4844:
The in-place version of quicksort has a space complexity of
2466:
In the most balanced case, a single quicksort call involves
2184:
flips is highly improbable (this can be made rigorous using
1490:// Choose the middle element as the pivot (integer division)
833:// If the current element is less than or equal to the pivot
8023:"Animated Sorting Algorithms: Quick Sort (3-way partition)"
6939:
Chandramouli, Badrish; Goldstein, Jonathan (18 June 2014).
6174:
3080:{\displaystyle nC(n)-(n-1)C(n-1)=n(n-1)-(n-1)(n-2)+2C(n-1)}
2173:
flips are required, and the chance that the coin won't get
540:
365:) is defined. It is a comparison-based sort since elements
331:
for randomized data, particularly on larger distributions.
7596:. ESA 2006: 14th Annual European Symposium on Algorithms.
7542:
International Journal of Computer and Information Sciences
6835:
6716:
Beautiful Code: Leading Programmers Explain How They Think
7587:
Kaligosi, Kanela; Sanders, Peter (11–13 September 2006).
7207:
Parallelized Quicksort and Radixsort with Optimal Speedup
6199:
smallest or largest elements from the rest of the input.
5680:
write buffer, the pivot record is appended to it and the
5620:
buffer is filled, it is written to the file and the next
4841:
The space used by quicksort depends on the version used.
1636:
first into the smaller side of the partition, then use a
724:(inclusive) are less than the pivot, and the elements at
529:
Communications of the Association for Computing Machinery
7865:. Pages 113–122 of section 5.2.2: Sorting by Exchanging.
7209:. Proc. Int'l Conf. on Parallel Computing Technologies.
7181:
Algorithms sequential & parallel: a unified approach
6947:. Sigmod '14. Snowbird Utah USA: ACM. pp. 731–742.
6664:"Algorithms 402: Increasing the Efficiency of Quicksort"
2554:{\displaystyle T(n)=O(n)+2T\left({\frac {n}{2}}\right).}
1936:{\displaystyle \textstyle \sum _{i=0}^{n}(n-i)=O(n^{2})}
319:. Quicksort was developed by British computer scientist
7539:
7413:
Engineering Java 7's Dual Pivot Quicksort Using MaLiJAn
2617:. Then the resulting parts of the partition have sizes
1099:
Subsequent recursions (expansion on previous paragraph)
956:
lo >= 0 && hi >= 0 && lo < hi
686:
first. Here we mention two specific partition methods.
7355:
Average case analysis of Java 7's dual pivot quicksort
7147:
Parallel and Sequential Data Structures and Algorithms
7044:
7042:
6195:
Several variants of quicksort exist that separate the
5540:
buffers other than the pivot record are copied to the
4597:
is also a random permutation, so the probability that
1873:
1474:
quicksort(A, lo, lt - 1) quicksort(A, gt + 1, hi)
1052:
partitioning also would cause Quicksort to degrade to
7410:
6938:
6349:
6302:
6262:
6216:
5899:
5879:
5815:
5767:
5746:
5726:
5706:
5686:
5666:
5646:
5626:
5606:
5586:
5566:
5546:
5526:
5506:
5486:
5466:
5446:
5426:
5389:
5366:
5343:
4698:
4657:
4630:
4603:
4525:
4460:
4430:
4403:
4376:
4349:
4281:
4178:
4142:
4108:
4081:
4048:
3983:
3914:
3846:
3182:
3096:
2947:
2846:
2655:
2493:
2320:
2194:
2108:
1872:
1543:// Swap the elements at the equal and greater indices
1274:
441:
393:
269:
239:
190:
149:
109:
62:
6399:
6184:
2243:, and each level of the call tree processes at most
2020:
factor). The result is that the algorithm uses only
1514:// Swap the elements at the equal and lesser indices
7039:
5720:write buffer, the pivot record is prepended to the
4951:From a bit complexity viewpoint, variables such as
4343:intervals. The core structural observation is that
2931:{\displaystyle nC(n)=n(n-1)+2\sum _{i=0}^{n-1}C(i)}
2143:times before reaching lists of size 1, yielding an
1240:Median-of-three code snippet for Lomuto partition:
681:
equal to the pivot, these can be excluded as well.)
7247:Edelkamp, Stefan; Weiß, Armin (7–8 January 2019).
6372:
6335:
6288:
6248:
6173:The BlockQuicksort technique is incorporated into
5921:
5885:
5865:
5801:
5752:
5732:
5712:
5692:
5672:
5652:
5632:
5612:
5592:
5572:
5552:
5532:
5512:
5492:
5472:
5452:
5432:
5412:
5375:
5352:
4825:
4678:
4643:
4616:
4589:
4511:
4443:
4424:falls inside one of the two intervals adjacent to
4416:
4389:
4362:
4328:
4250:
4160:
4121:
4094:
4067:
4034:
3965:
3908:Consider a BST created by insertion of a sequence
3897:
3723:
3165:
3079:
2930:
2831:
2553:
2426:{\displaystyle T(n)=O(n)+T(0)+T(n-1)=O(n)+T(n-1).}
2425:
2224:
2135:
1935:
1806:processors by performing partitioning implicitly.
1779:described a parallelized quicksort (and a related
1497:// Iterate and compare all elements with the pivot
1032:// Swap the elements at the left and right indices
463:
419:
290:
254:
214:
164:
133:
84:
8042:Open Data Structures – Section 11.1.2 – Quicksort
7336:"Changing std::sort at Google's Scale and Beyond"
5985:as for standard quicksort, given for unique keys
4590:{\displaystyle (x_{1},x_{2},\ldots ,x_{j},x_{i})}
2566:master theorem for divide-and-conquer recurrences
479:The quicksort algorithm was developed in 1959 by
8540:
7824:"Introspective Sorting and Selection Algorithms"
7249:Worst-Case Efficient Sorting with QuickMergesort
6982:
6980:
6884:(Thesis). Technische Universität Kaiserslautern.
4880:space. Then the other partition is sorted using
4223:
4035:{\displaystyle C=\sum _{i}\sum _{j<i}c_{i,j}}
3977:denote the cost of creation of the BST. We have
1495:lt := lo eq := lo gt := hi
1314:, a recursive median-of-three (Mo3), defined as
7586:
7329:
7327:
5018:
2477:work plus two recursive calls on lists of size
2300:work plus two recursive calls on lists of size
2285:factor, the time needed to sort a list of size
1288:. Median-of-three pivoting brings this down to
1154:Let's first examine the choice of recursing on
7954:
7641:"The average case analysis of Partition sorts"
7089:
7087:
7085:
6612:
5316:, as the standard algorithm to sort arrays of
5023:Quicksort is a space-optimized version of the
1658:-sorted, meaning that each element is at most
1609:subroutine takes no longer than linear time).
8078:
7922:
7519:Multi-Pivot Quicksort: Theory and Experiments
7493:Multi-Pivot Quicksort: Theory and Experiments
7093:
6977:
6613:Bentley, Jon L.; McIlroy, M. Douglas (1993).
6608:
6606:
6604:
6602:
6600:
6598:
6596:
3831:
2009:calls at each level, this is subsumed in the
7618:
7385:
7324:
7246:
5932:
3973:of values forming a random permutation. Let
1673:time to finish the sort, which is linear if
1007:// the right index is greater than the pivot
871:Sorting the entire array is accomplished by
7663:(1978). "Implementing Quicksort programs".
7177:
7082:
7052:(1978). "Implementing Quicksort programs".
7010:
6813:
5178:
5047:The most direct competitor of quicksort is
4512:{\displaystyle (x_{1},x_{2},\ldots ,x_{n})}
4329:{\displaystyle {x_{1},x_{2},\ldots ,x_{j}}}
3966:{\displaystyle (x_{1},x_{2},\ldots ,x_{n})}
3898:{\displaystyle (x_{1},x_{2},\ldots ,x_{n})}
1255:A < A swap A with A pivot := A
903:The original partition scheme described by
8085:
8071:
7590:How Branch Mispredictions Affect Quicksort
7575:Parallel Unification: Practical Complexity
7353:Wild, Sebastian; Nebel, Markus E. (2012).
7223:
6745:"Quicksort Partitioning: Hoare vs. Lomuto"
6593:
6529:Algorithms, Abstraction and Implementation
6027:algorithm. This is again a combination of
5866:{\displaystyle {\frac {1+\ln(N+1)}{(4B)}}}
789:// Partition array and get the pivot index
712:as it scans the array using another index
689:
27:
8002:"Animated Sorting Algorithms: Quick Sort"
7968:
7937:
7905:. Chapter 7: Quicksort, pp. 145–164.
7802:
7711:
7659:
7624:
7500:
7475:
7362:
7352:
7256:
7214:
7158:
7107:
7048:
6986:
6915:
6679:
6661:
6630:
6440:. Computer History Museum. Archived from
878:
851:// Move the temporary pivot index forward
499:. After recognizing that his first idea,
5289:
3788:explained in the article Comparison sort
2038:
1218:
993:// the left index is less than the pivot
976:// Choose the first element as the pivot
882:
620:
350:, requiring small additional amounts of
7857:, Third Edition. Addison-Wesley, 1997.
7333:
6768:
6710:
6548:
6461:
6459:
4888:, and keeps the stack depth bounded by
2270:An alternative approach is to set up a
2062:time in expectation, averaged over all
1798:(concurrent read and concurrent write)
1275:§ Analysis of randomized quicksort
1204:follows the exact same logic as above.
855:// Swap the pivot with the last element
815:// Choose the last element as the pivot
553:and in the reference implementation of
487:. At that time, Hoare was working on a
8541:
8092:
7818:
7311:
7204:
7178:Miller, Russ; Boxer, Laurence (2000).
6497:
6336:{\displaystyle {\Theta }(n\log ^{2}n)}
5383:the number of records per buffer, and
3166:{\displaystyle nC(n)=(n+1)C(n-1)+2n-2}
1814:
1802:(parallel random-access machine) with
1476:// Divides array into three partitions
778:// Ensure indices are in correct order
8066:
8051:Interactive illustration of Quicksort
7780:
7754:
7720:
7296:
7161:"Quicksort Partition via Prefix Scan"
6894:
6831:
6829:
6827:
6825:
6809:
6807:
6739:
6737:
6735:
6589:. Marcelo M De Barros. 15 March 2015.
6491:
6465:
5996:is a hidden constant in all standard
5331:
2594:The outline of a formal proof of the
1957:
752:, a quicksort that sorts elements at
7693:
7469:
7357:. European Symposium on Algorithms.
6877:
6662:Van Emden, M. H. (1 November 1970).
6456:
5700:buffer written. If that buffer is a
5560:write buffer in ascending order and
4959:do not use constant space; it takes
2632:, and i is uniform random from 0 to
2265:
2093:
1575:// Return lesser and greater indices
1470:lt, gt := partition(A, lo, hi)
1422:
962:// Divides array into two partitions
804:// Divides array into two partitions
520:Volume 5, Issue 1, 1962, Pages 10–16
172:(three-way partition and equal keys)
16:Divide and conquer sorting algorithm
7724:(1961). "Algorithm 63: Partition".
7647:3221, Springer Verlag, pp. 240–251.
6469:(1961). "Algorithm 64: Quicksort".
6007:
5943:This algorithm is a combination of
5305:pivots. While the dual-pivot case (
4836:
2232:. But if its average call depth is
2047:distinct elements, quicksort takes
483:while he was a visiting student at
13:
7639:Richard Cole, David C. Kandathil:
7379:
7320:from the original on 1 April 2009.
7314:"Heapsort, Quicksort, and Entropy"
7143:Quicksort and Sorting Lower Bounds
6822:
6804:
6771:"A killer adversary for quicksort"
6732:
6304:
6296:operations; at worst they perform
6289:{\displaystyle {\Theta }(n\log n)}
6264:
4699:
4179:
4161:{\displaystyle \operatorname {E} }
4143:
3695:
1943:, so in that case quicksort takes
1809:
1685:
1493:// Lesser, equal and greater index
1223:
791:p := partition(A, lo, hi)
14:
8570:
7994:
7957:Software: Practice and Experience
7828:Software: Practice and Experience
7645:Lecture Notes in Computer Science
7334:Kutenin, Danila (20 April 2022).
6996:(3 ed.). Pearson Education.
6778:Software: Practice and Experience
6619:Software: Practice and Experience
6202:
6185:Partial and incremental quicksort
6148:
6053:algorithms implicitly assume the
4689:We end with a short calculation:
2436:This is the same relation as for
1706:, the partitioning step performs
1466:lo >= 0 && lo < hi
1277:) with random pivot selection is
1087:(elements ≥ pivot) as opposed to
1018:// If the indices crossed, return
663:Otherwise pick a value, called a
642:diagram on large sets of numbers.
342:. The sub-arrays are then sorted
315:is an efficient, general-purpose
6769:McIlroy, M. D. (10 April 1999).
6420: – Hybrid sorting algorithm
6402:
4937:nested recursive calls and need
4915:nested recursive calls, it uses
4679:{\displaystyle {\frac {2}{j+1}}}
4397:in the algorithm if and only if
2484:, so the recurrence relation is
2311:, so the recurrence relation is
1612:
748:for small arrays, and so on. In
8108:Computational complexity theory
8059:, a beginner-friendly deep-dive
7851:The Art of Computer Programming
7809:(Reprinted in Hoare and Jones:
7633:
7612:
7580:
7567:
7533:
7509:
7484:
7463:
7437:
7404:
7386:Yaroslavskiy, Vladimir (2009).
7346:
7312:MacKay, David (December 2005).
7305:
7290:
7240:
7198:
7171:
7152:
7135:
7028:
6932:
6888:
6871:
6762:
6101:but elements are unique within
6012:Also developed by Powers as an
5929:for worst case internal sort).
5802:{\displaystyle O(\log _{2}(n))}
5360:number of records in the file,
3782:comparisons on average to sort
1212:), and an already sorted array
7758:(1961). "Algorithm 65: Find".
7229:The other one may either have
6818:. Addison-Wesley Professional.
6718:. O'Reilly Media. p. 30.
6704:
6655:
6579:
6542:
6521:
6430:
6367:
6355:
6330:
6308:
6283:
6268:
6249:{\displaystyle n\log n+{O}(n)}
6243:
6237:
5916:
5903:
5857:
5848:
5843:
5831:
5796:
5793:
5787:
5771:
5221:A variant of quickselect, the
5148:Merge sort works very well on
4817:
4802:
4711:
4705:
4584:
4526:
4506:
4461:
4245:
4226:
4191:
4185:
4155:
4149:
3960:
3915:
3892:
3847:
3569:
3563:
3482:
3470:
3431:
3419:
3380:
3368:
3322:
3310:
3295:
3283:
3241:
3229:
3199:
3193:
3145:
3133:
3127:
3115:
3109:
3103:
3074:
3062:
3050:
3038:
3035:
3023:
3017:
3005:
2996:
2984:
2978:
2966:
2960:
2954:
2925:
2919:
2880:
2868:
2859:
2853:
2826:
2820:
2762:
2759:
2741:
2732:
2726:
2720:
2665:
2659:
2518:
2512:
2503:
2497:
2444:, and it solves to worst case
2417:
2405:
2396:
2390:
2381:
2369:
2360:
2354:
2345:
2339:
2330:
2324:
1929:
1916:
1907:
1895:
1866:work to do the partition, and
1262:first, then that new value of
1046:quicksort(A, 0, length(A) - 1)
1044:The entire array is sorted by
873:quicksort(A, 0, length(A) - 1)
458:
445:
414:
397:
285:
273:
249:
243:
209:
194:
159:
153:
128:
113:
79:
66:
1:
8559:Divide-and-conquer algorithms
7653:
6881:Java 7's Dual Pivot Quicksort
6615:"Engineering a sort function"
5093:Quicksort also competes with
4970:bits to index into a list of
3734:Solving the recurrence gives
2225:{\displaystyle 2\log _{4/3}n}
522:. Later, Hoare learned about
7700:Discrete Applied Mathematics
7205:Powers, David M. W. (1991).
5873:, but worst case pattern is
5019:Relation to other algorithms
2136:{\displaystyle \log _{4/3}n}
1243:mid := ⌊(lo + hi) / 2⌋
648:divide-and-conquer algorithm
616:
493:National Physical Laboratory
420:{\displaystyle O(n\log {n})}
336:divide-and-conquer algorithm
7:
8057:Fast Sorting with Quicksort
7812:Essays in computing science
6504:The Algorithm Design Manual
6410:Computer programming portal
6395:
6373:{\displaystyle {O}(\log n)}
6166:(which fit easily into the
6087:time using a hash table or
5284:
3905:form a random permutation.
1438:Dutch national flag problem
1251:A < A swap A with A
1247:A < A swap A with A
1196:The choice of recursing on
10:
8575:
8416:Batcher odd–even mergesort
7886:Introduction to Algorithms
7233:element or be empty (have
6854:Introduction to Algorithms
6188:
6076:is smaller we can sort in
5936:
5298:number of subarrays using
5254:More abstractly, given an
4102:there was a comparison to
3832:Using a binary search tree
2084:Introduction to Algorithms
793:// Sort the two partitions
716:such that the elements at
705:Introduction to Algorithms
591:Introduction to Algorithms
474:
215:{\displaystyle O(n\log n)}
134:{\displaystyle O(n\log n)}
8510:
8477:
8434:
8403:
8342:
8311:
8270:
8222:
8176:
8100:
8018:– graphical demonstration
7948:10.1137/S0097539700382108
7713:10.1016/j.dam.2005.07.005
7502:10.1137/1.9781611973198.6
7421:10.1137/1.9781611972931.5
7267:10.1137/1.9781611975499.1
6507:. Springer. p. 129.
5933:Three-way radix quicksort
4519:is a random permutation,
1554:// Decrease greater index
1472:// Multiple return values
783:lo >= hi || lo < 0
383:of quicksort shows that,
302:
291:{\displaystyle O(\log n)}
225:
176:
95:
48:
38:
26:
8421:Pairwise sorting network
7525:(Seminar presentation).
7159:Breshears, Clay (2012).
6878:Wild, Sebastian (2012).
6424:
5922:{\displaystyle O(n^{2})}
5179:Selection-based pivoting
5167:network-attached storage
4134:linearity of expectation
3796:Stirling's approximation
1527:lt := lt + 1
1525:// Increase lesser index
1113:Consider the example of
818:// Temporary pivot index
799:quicksort(A, p + 1, hi)
795:quicksort(A, lo, p - 1)
760:(inclusive) of an array
464:{\displaystyle O(n^{2})}
354:to perform the sorting.
85:{\displaystyle O(n^{2})}
8449:Kirkpatrick–Reisch sort
8053:, with code walkthrough
6953:10.1145/2588555.2593662
6565:10.1145/1467247.1467261
5952:bits, the best case is
4068:{\displaystyle c_{i,j}}
3790:) and in case of large
1571:// Increase equal index
1529:// Increase equal index
1095:as in Lomuto's scheme.
1083:(elements ≤ pivot) and
690:Lomuto partition scheme
646:Quicksort is a type of
485:Moscow State University
340:partition-exchange sort
8329:Oscillating merge sort
8209:Proportion extend sort
8163:Transdichotomous model
7979:10.1002/spe.4380231105
7388:"Dual-Pivot Quicksort"
7301:. azillionmonkeys.com.
7118:10.1006/jagm.1998.0985
6941:"Patience is a virtue"
6851:(2009) . "Quicksort".
6641:10.1002/spe.4380231105
6374:
6337:
6290:
6250:
6055:transdichotomous model
5923:
5893:passes (equivalent to
5887:
5867:
5803:
5754:
5734:
5714:
5694:
5674:
5654:
5634:
5614:
5594:
5574:
5554:
5534:
5514:
5494:
5474:
5454:
5434:
5414:
5413:{\displaystyle M=N/B=}
5377:
5354:
4827:
4680:
4645:
4618:
4591:
4513:
4445:
4418:
4391:
4364:
4336:, once sorted, define
4330:
4252:
4162:
4123:
4096:
4069:
4036:
3967:
3899:
3725:
3652:
3601:
3167:
3081:
2932:
2915:
2833:
2816:
2719:
2555:
2427:
2226:
2137:
1937:
1894:
1783:) that can operate in
1556:gt := gt - 1
1531:eq := eq + 1
1258:It puts a median into
900:
879:Hoare partition scheme
801:// Right side of pivot
643:
584:that he attributed to
465:
421:
387:, the algorithm takes
298:auxiliary (Hoare 1962)
292:
256:
216:
166:
135:
86:
8490:Pre-topological order
7913:Analysis of Quicksort
7855:Sorting and Searching
7804:10.1093/comjnl/5.1.10
7774:10.1145/366622.366647
7740:10.1145/366622.366642
7679:10.1145/359619.359631
7096:Journal of Algorithms
7068:10.1145/359619.359631
6917:10.1093/comjnl/5.1.10
6841:Leiserson, Charles E.
6681:10.1145/362790.362803
6485:10.1145/366622.366644
6375:
6338:
6291:
6251:
6156:branch mispredictions
5924:
5888:
5868:
5804:
5755:
5735:
5715:
5695:
5675:
5655:
5635:
5615:
5595:
5575:
5555:
5535:
5515:
5495:
5475:
5455:
5435:
5415:
5378:
5355:
5290:Multi-pivot quicksort
5127:auxiliary space (vs.
5072:locality of reference
4828:
4681:
4646:
4644:{\displaystyle x_{j}}
4619:
4617:{\displaystyle x_{i}}
4592:
4514:
4446:
4444:{\displaystyle x_{j}}
4419:
4417:{\displaystyle x_{i}}
4392:
4390:{\displaystyle x_{j}}
4365:
4363:{\displaystyle x_{i}}
4331:
4253:
4163:
4136:, the expected value
4124:
4122:{\displaystyle x_{j}}
4097:
4095:{\displaystyle x_{i}}
4070:
4037:
3968:
3900:
3770:cannot use less than
3726:
3626:
3581:
3168:
3082:
2933:
2889:
2834:
2790:
2693:
2556:
2428:
2227:
2138:
2039:Average-case analysis
1938:
1874:
1840:is a linear chain of
1621:To make sure at most
1481:partition(A, lo, hi)
1459:quicksort(A, lo, hi)
1323:) = median(Mo3(first
1219:Implementation issues
967:partition(A, lo, hi)
949:quicksort(A, lo, hi)
886:
809:partition(A, lo, hi)
797:// Left side of pivot
773:quicksort(A, lo, hi)
764:can be expressed as:
624:
577:pseudomedian of nine,
466:
422:
381:Mathematical analysis
293:
257:
217:
167:
136:
87:
8469:Merge-insertion sort
8334:Polyphase merge sort
8189:Cocktail shaker sort
7873:Charles E. Leiserson
7694:Dean, B. C. (2006).
7573:David M. W. Powers,
7297:Hsieh, Paul (2004).
6990:(1 September 1998).
6904:The Computer Journal
6814:Jon Bentley (1999).
6749:cs.stackexchange.com
6347:
6300:
6260:
6214:
6004:equal to the pivot.
5897:
5877:
5813:
5765:
5744:
5724:
5704:
5684:
5664:
5644:
5624:
5604:
5584:
5564:
5544:
5524:
5504:
5484:
5464:
5444:
5424:
5387:
5364:
5341:
4696:
4655:
4628:
4601:
4523:
4458:
4428:
4401:
4374:
4347:
4279:
4176:
4140:
4106:
4079:
4046:
3981:
3912:
3844:
3180:
3094:
2945:
2844:
2653:
2491:
2318:
2192:
2106:
2043:To sort an array of
1870:
1681:in modern computers.
1573:eq := eq + 1
981:i := lo - 1
517:The Computer Journal
439:
427:comparisons to sort
391:
267:
255:{\displaystyle O(n)}
237:
188:
165:{\displaystyle O(n)}
147:
107:
60:
8485:Topological sorting
8247:Cartesian tree sort
7606:10.1007/11841036_69
7373:2013arXiv1310.7409W
7299:"Sorting revisited"
5963:and the worst case
5939:Multi-key quicksort
5320:(sorting arrays of
5218:in the worst case.
5185:selection algorithm
4454:Observe that since
3683:
2272:recurrence relation
1815:Worst-case analysis
1700:parallel prefix sum
985:j := hi + 1
489:machine translation
346:. This can be done
23:
8375:Interpolation sort
8350:American flag sort
8343:Distribution sorts
8324:Cascade merge sort
8094:Sorting algorithms
7917:Swansea University
7889:, Second Edition.
7554:10.1007/BF00996816
7449:Java Platform SE 7
7400:on 2 October 2015.
7340:Experimental chill
6898:(1 January 1962).
6816:Programming Pearls
6438:"Sir Antony Hoare"
6370:
6333:
6286:
6246:
5919:
5883:
5863:
5799:
5750:
5730:
5710:
5690:
5670:
5650:
5630:
5610:
5590:
5570:
5550:
5530:
5510:
5490:
5470:
5450:
5430:
5410:
5376:{\displaystyle B=}
5373:
5353:{\displaystyle N=}
5350:
5332:External quicksort
4823:
4781:
4742:
4726:
4676:
4641:
4614:
4587:
4509:
4441:
4414:
4387:
4360:
4326:
4248:
4222:
4206:
4158:
4119:
4092:
4065:
4032:
4015:
3999:
3963:
3895:
3838:binary search tree
3721:
3719:
3669:
3163:
3077:
2928:
2829:
2551:
2423:
2222:
2133:
1958:Best-case analysis
1933:
1932:
1847:nested calls. The
1765:additional space.
1725:time and requires
1174:when recursing on
901:
867:// the pivot index
853:i := i + 1
696:Programming Pearls
644:
582:Programming Pearls
545:C standard library
461:
417:
288:
252:
212:
162:
141:(simple partition)
131:
82:
21:
8549:1961 in computing
8536:
8535:
8511:Impractical sorts
7963:(11): 1249–1265.
7527:Waterloo, Ontario
7430:978-1-61197-253-5
7276:978-1-61197-549-9
7191:978-0-13-086373-7
7184:. Prentice Hall.
7003:978-81-317-1291-7
6988:Sedgewick, Robert
6962:978-1-4503-2376-5
6845:Rivest, Ronald L.
6837:Cormen, Thomas H.
6725:978-0-596-51004-6
6625:(11): 1249–1265.
6514:978-1-84800-069-8
6499:Skiena, Steven S.
6160:data dependencies
5886:{\displaystyle N}
5861:
5753:{\displaystyle Y}
5733:{\displaystyle Y}
5713:{\displaystyle Y}
5693:{\displaystyle X}
5673:{\displaystyle X}
5653:{\displaystyle Y}
5633:{\displaystyle X}
5613:{\displaystyle Y}
5593:{\displaystyle X}
5573:{\displaystyle Y}
5553:{\displaystyle X}
5533:{\displaystyle Y}
5513:{\displaystyle X}
5493:{\displaystyle Y}
5473:{\displaystyle X}
5453:{\displaystyle Y}
5433:{\displaystyle X}
5223:median of medians
5066:, but heapsort's
5029:sorting algorithm
4948:auxiliary space.
4772:
4759:
4727:
4717:
4674:
4207:
4197:
4000:
3990:
3692:
3661:
3618:
3576:
3543:
3540:
3531:
3510:
3497:
3459:
3438:
3408:
3395:
3350:
3329:
3299:
3269:
3248:
3214:
2788:
2691:
2542:
2266:Using recurrences
2094:Using percentiles
2075:equal probability
1423:Repeated elements
1016:A > pivot
1002:A < pivot
317:sorting algorithm
310:
309:
262:auxiliary (naive)
43:Sorting algorithm
8566:
8554:Comparison sorts
8444:Block merge sort
8404:Concurrent sorts
8303:Patience sorting
8087:
8080:
8073:
8064:
8063:
8038:
8036:
8034:
8025:. Archived from
8017:
8015:
8013:
8004:. Archived from
7990:
7972:
7951:
7941:
7877:Ronald L. Rivest
7869:Thomas H. Cormen
7843:
7820:Musser, David R.
7808:
7806:
7777:
7751:
7717:
7715:
7690:
7648:
7637:
7631:
7630:
7628:
7616:
7610:
7609:
7595:
7584:
7578:
7571:
7565:
7564:
7537:
7531:
7530:
7524:
7513:
7507:
7506:
7504:
7488:
7482:
7481:
7479:
7467:
7461:
7460:
7458:
7456:
7441:
7435:
7434:
7408:
7402:
7401:
7399:
7393:. Archived from
7392:
7383:
7377:
7376:
7366:
7350:
7344:
7343:
7331:
7322:
7321:
7309:
7303:
7302:
7294:
7288:
7287:
7260:
7244:
7238:
7236:
7232:
7227:
7221:
7220:
7218:
7202:
7196:
7195:
7175:
7169:
7168:
7156:
7150:
7139:
7133:
7132:
7111:
7091:
7080:
7079:
7046:
7037:
7032:
7026:
7014:
7008:
7007:
6984:
6975:
6974:
6936:
6930:
6929:
6919:
6892:
6886:
6885:
6875:
6869:
6868:
6833:
6820:
6819:
6811:
6802:
6801:
6775:
6766:
6760:
6759:
6757:
6755:
6741:
6730:
6729:
6708:
6702:
6701:
6683:
6659:
6653:
6652:
6634:
6610:
6591:
6590:
6583:
6577:
6576:
6546:
6540:
6525:
6519:
6518:
6495:
6489:
6488:
6463:
6454:
6453:
6451:
6449:
6434:
6412:
6407:
6406:
6379:
6377:
6376:
6371:
6354:
6342:
6340:
6339:
6334:
6323:
6322:
6307:
6295:
6293:
6292:
6287:
6267:
6255:
6253:
6252:
6247:
6236:
6198:
6144:
6133:
6122:
6111:
6100:
6086:
6075:
6071:
6060:
6048:
6045:
6041:
6022:
6008:Quick radix sort
5995:
5991:
5984:
5973:
5962:
5951:
5928:
5926:
5925:
5920:
5915:
5914:
5892:
5890:
5889:
5884:
5872:
5870:
5869:
5864:
5862:
5860:
5846:
5817:
5808:
5806:
5805:
5800:
5783:
5782:
5759:
5757:
5756:
5751:
5739:
5737:
5736:
5731:
5719:
5717:
5716:
5711:
5699:
5697:
5696:
5691:
5679:
5677:
5676:
5671:
5659:
5657:
5656:
5651:
5639:
5637:
5636:
5631:
5619:
5617:
5616:
5611:
5599:
5597:
5596:
5591:
5579:
5577:
5576:
5571:
5559:
5557:
5556:
5551:
5539:
5537:
5536:
5531:
5519:
5517:
5516:
5511:
5499:
5497:
5496:
5491:
5479:
5477:
5476:
5471:
5459:
5457:
5456:
5451:
5439:
5437:
5436:
5431:
5419:
5417:
5416:
5411:
5403:
5382:
5380:
5379:
5374:
5359:
5357:
5356:
5351:
5311:
5304:
5297:
5279:
5264:
5250:
5235:
5217:
5206:
5190:
5159:external sorting
5144:
5137:
5126:
5111:
5084:
5065:
5042:
5025:binary tree sort
5013:
4999:
4984:
4973:
4969:
4947:
4936:
4925:
4914:
4898:
4879:
4865:
4854:
4837:Space complexity
4832:
4830:
4829:
4824:
4795:
4791:
4780:
4760:
4758:
4744:
4741:
4725:
4685:
4683:
4682:
4677:
4675:
4673:
4659:
4650:
4648:
4647:
4642:
4640:
4639:
4623:
4621:
4620:
4615:
4613:
4612:
4596:
4594:
4593:
4588:
4583:
4582:
4570:
4569:
4551:
4550:
4538:
4537:
4518:
4516:
4515:
4510:
4505:
4504:
4486:
4485:
4473:
4472:
4450:
4448:
4447:
4442:
4440:
4439:
4423:
4421:
4420:
4415:
4413:
4412:
4396:
4394:
4393:
4388:
4386:
4385:
4369:
4367:
4366:
4361:
4359:
4358:
4342:
4335:
4333:
4332:
4327:
4325:
4324:
4323:
4305:
4304:
4292:
4291:
4274:
4264:
4257:
4255:
4254:
4249:
4244:
4243:
4221:
4205:
4171:
4167:
4165:
4164:
4159:
4128:
4126:
4125:
4120:
4118:
4117:
4101:
4099:
4098:
4093:
4091:
4090:
4074:
4072:
4071:
4066:
4064:
4063:
4041:
4039:
4038:
4033:
4031:
4030:
4014:
3998:
3976:
3972:
3970:
3969:
3964:
3959:
3958:
3940:
3939:
3927:
3926:
3904:
3902:
3901:
3896:
3891:
3890:
3872:
3871:
3859:
3858:
3827:
3793:
3785:
3781:
3762:
3730:
3728:
3727:
3722:
3720:
3698:
3693:
3685:
3682:
3677:
3662:
3654:
3651:
3640:
3619:
3617:
3603:
3600:
3595:
3577:
3572:
3558:
3550:
3541:
3538:
3536:
3532:
3530:
3516:
3511:
3503:
3498:
3496:
3485:
3465:
3460:
3458:
3444:
3439:
3437:
3414:
3409:
3401:
3396:
3394:
3383:
3363:
3355:
3351:
3349:
3335:
3330:
3325:
3305:
3300:
3298:
3275:
3270:
3268:
3254:
3249:
3244:
3224:
3215:
3213:
3202:
3188:
3172:
3170:
3169:
3164:
3086:
3084:
3083:
3078:
2937:
2935:
2934:
2929:
2914:
2903:
2838:
2836:
2835:
2830:
2815:
2804:
2789:
2781:
2718:
2707:
2692:
2684:
2645:
2638:
2631:
2620:
2616:
2608:
2590:
2560:
2558:
2557:
2552:
2547:
2543:
2535:
2483:
2476:
2462:
2432:
2430:
2429:
2424:
2310:
2303:
2299:
2288:
2284:
2261:
2246:
2242:
2231:
2229:
2228:
2223:
2215:
2214:
2210:
2183:
2176:
2172:
2165:
2157:
2142:
2140:
2139:
2134:
2126:
2125:
2121:
2087:, Section 7.3).
2072:
2069:permutations of
2068:
2061:
2046:
2034:
2019:
2008:
1997:
1986:
1972:
1953:
1942:
1940:
1939:
1934:
1928:
1927:
1893:
1888:
1865:
1850:
1846:
1835:
1825:
1805:
1793:
1777:David M W Powers
1764:
1756:
1748:
1736:
1732:
1724:
1713:
1705:
1696:task parallelism
1676:
1672:
1661:
1657:
1653:
1631:
1608:
1604:
1591:
1586:
1488:pivot := A
1445:
1418:
1403:
1390:integer overflow
1384:
1378:
1376:
1375:
1372:
1369:
1358:
1356:
1355:
1352:
1349:
1338:
1336:
1335:
1332:
1329:
1309:
1287:
1272:
1265:
1261:
1203:
1199:
1191:
1181:
1177:
1168:
1161:
1157:
1134:
1130:
1126:
1122:
1107:
1094:
1090:
1086:
1082:
1078:
1062:
1047:
1012:j := j - 1
998:i := i + 1
974:pivot := A
931:
921:
898:
894:
890:
874:
813:pivot := A
763:
759:
755:
742:
731:
727:
723:
719:
715:
711:
636:
612:
604:
561:Robert Sedgewick
552:
491:project for the
470:
468:
467:
462:
457:
456:
426:
424:
423:
418:
413:
297:
295:
294:
289:
261:
259:
258:
253:
230:space complexity
221:
219:
218:
213:
171:
169:
168:
163:
140:
138:
137:
132:
91:
89:
88:
83:
78:
77:
31:
24:
20:
8574:
8573:
8569:
8568:
8567:
8565:
8564:
8563:
8539:
8538:
8537:
8532:
8506:
8497:Pancake sorting
8473:
8430:
8399:
8380:Pigeonhole sort
8338:
8307:
8271:Insertion sorts
8266:
8252:Tournament sort
8224:Selection sorts
8218:
8172:
8153:Integer sorting
8148:Sorting network
8138:Comparison sort
8096:
8091:
8032:
8030:
8029:on 6 March 2015
8021:
8011:
8009:
8008:on 2 March 2015
8000:
7997:
7926:SIAM J. Comput.
7782:Hoare, C. A. R.
7756:Hoare, C. A. R.
7722:Hoare, C. A. R.
7673:(10): 847–857.
7656:
7651:
7638:
7634:
7617:
7613:
7593:
7585:
7581:
7572:
7568:
7538:
7534:
7522:
7514:
7510:
7489:
7485:
7468:
7464:
7454:
7452:
7443:
7442:
7438:
7431:
7409:
7405:
7397:
7390:
7384:
7380:
7351:
7347:
7332:
7325:
7310:
7306:
7295:
7291:
7277:
7245:
7241:
7234:
7230:
7228:
7224:
7203:
7199:
7192:
7176:
7172:
7157:
7153:
7140:
7136:
7092:
7083:
7062:(10): 847–857.
7047:
7040:
7033:
7029:
7015:
7011:
7004:
6985:
6978:
6963:
6937:
6933:
6896:Hoare, C. A. R.
6893:
6889:
6876:
6872:
6865:
6849:Stein, Clifford
6834:
6823:
6812:
6805:
6773:
6767:
6763:
6753:
6751:
6743:
6742:
6733:
6726:
6709:
6705:
6674:(11): 693–694.
6660:
6656:
6611:
6594:
6585:
6584:
6580:
6547:
6543:
6526:
6522:
6515:
6496:
6492:
6467:Hoare, C. A. R.
6464:
6457:
6447:
6445:
6444:on 3 April 2015
6436:
6435:
6431:
6427:
6408:
6401:
6398:
6350:
6348:
6345:
6344:
6318:
6314:
6303:
6301:
6298:
6297:
6263:
6261:
6258:
6257:
6232:
6215:
6212:
6211:
6205:
6196:
6193:
6191:Partial sorting
6187:
6151:
6135:
6124:
6113:
6102:
6092:
6089:integer sorting
6077:
6073:
6062:
6058:
6051:comparison sort
6049:-bit keys. All
6046:
6043:
6032:
6013:
6010:
5998:comparison sort
5993:
5986:
5975:
5964:
5953:
5949:
5941:
5935:
5910:
5906:
5898:
5895:
5894:
5878:
5875:
5874:
5847:
5818:
5816:
5814:
5811:
5810:
5778:
5774:
5766:
5763:
5762:
5745:
5742:
5741:
5740:buffer and the
5725:
5722:
5721:
5705:
5702:
5701:
5685:
5682:
5681:
5665:
5662:
5661:
5645:
5642:
5641:
5625:
5622:
5621:
5605:
5602:
5601:
5585:
5582:
5581:
5565:
5562:
5561:
5545:
5542:
5541:
5525:
5522:
5521:
5505:
5502:
5501:
5485:
5482:
5481:
5465:
5462:
5461:
5445:
5442:
5441:
5425:
5422:
5421:
5399:
5388:
5385:
5384:
5365:
5362:
5361:
5342:
5339:
5338:
5334:
5306:
5299:
5295:
5292:
5287:
5266:
5255:
5237:
5226:
5208:
5197:
5188:
5181:
5145:for heapsort).
5139:
5128:
5117:
5098:
5075:
5052:
5033:
5021:
5004:
5000:bits of space.
4986:
4975:
4971:
4960:
4938:
4927:
4916:
4905:
4889:
4870:
4860:
4845:
4839:
4776:
4771:
4767:
4748:
4743:
4731:
4721:
4697:
4694:
4693:
4663:
4658:
4656:
4653:
4652:
4635:
4631:
4629:
4626:
4625:
4624:is adjacent to
4608:
4604:
4602:
4599:
4598:
4578:
4574:
4565:
4561:
4546:
4542:
4533:
4529:
4524:
4521:
4520:
4500:
4496:
4481:
4477:
4468:
4464:
4459:
4456:
4455:
4435:
4431:
4429:
4426:
4425:
4408:
4404:
4402:
4399:
4398:
4381:
4377:
4375:
4372:
4371:
4370:is compared to
4354:
4350:
4348:
4345:
4344:
4337:
4319:
4315:
4300:
4296:
4287:
4283:
4282:
4280:
4277:
4276:
4266:
4262:
4233:
4229:
4211:
4201:
4177:
4174:
4173:
4169:
4141:
4138:
4137:
4113:
4109:
4107:
4104:
4103:
4086:
4082:
4080:
4077:
4076:
4053:
4049:
4047:
4044:
4043:
4020:
4016:
4004:
3994:
3982:
3979:
3978:
3974:
3954:
3950:
3935:
3931:
3922:
3918:
3913:
3910:
3909:
3886:
3882:
3867:
3863:
3854:
3850:
3845:
3842:
3841:
3834:
3822:
3815:
3803:
3799:
3791:
3783:
3775:
3771:
3768:comparison sort
3758:
3735:
3718:
3717:
3694:
3684:
3678:
3673:
3653:
3641:
3630:
3607:
3602:
3596:
3585:
3559:
3557:
3548:
3547:
3534:
3533:
3520:
3515:
3502:
3486:
3466:
3464:
3448:
3443:
3418:
3413:
3400:
3384:
3364:
3362:
3353:
3352:
3339:
3334:
3306:
3304:
3279:
3274:
3258:
3253:
3225:
3223:
3216:
3203:
3189:
3187:
3183:
3181:
3178:
3177:
3095:
3092:
3091:
2946:
2943:
2942:
2904:
2893:
2845:
2842:
2841:
2805:
2794:
2780:
2708:
2697:
2683:
2654:
2651:
2650:
2640:
2633:
2622:
2618:
2611:
2595:
2569:
2534:
2530:
2492:
2489:
2488:
2478:
2467:
2445:
2319:
2316:
2315:
2305:
2301:
2290:
2286:
2275:
2268:
2248:
2244:
2233:
2206:
2202:
2198:
2193:
2190:
2189:
2186:Chernoff bounds
2178:
2174:
2167:
2163:
2144:
2117:
2113:
2109:
2107:
2104:
2103:
2096:
2070:
2063:
2048:
2044:
2041:
2021:
2010:
1999:
1988:
1982:
1978:
1968:
1964:
1960:
1944:
1923:
1919:
1889:
1878:
1871:
1868:
1867:
1852:
1848:
1841:
1830:
1820:
1817:
1812:
1810:Formal analysis
1803:
1784:
1758:
1750:
1738:
1734:
1726:
1715:
1707:
1703:
1692:parallelization
1688:
1686:Parallelization
1674:
1663:
1659:
1655:
1651:
1632:space is used,
1622:
1615:
1606:
1596:
1589:
1584:
1581:
1441:
1425:
1405:
1393:
1373:
1370:
1367:
1366:
1364:
1353:
1350:
1347:
1346:
1344:
1333:
1330:
1327:
1326:
1324:
1318:
1300:
1289:
1278:
1270:
1263:
1259:
1256:
1226:
1224:Choice of pivot
1221:
1201:
1197:
1189:
1179:
1175:
1166:
1159:
1155:
1132:
1128:
1124:
1120:
1105:
1092:
1088:
1084:
1080:
1065:
1053:
1045:
1042:
923:
913:
896:
892:
888:
881:
872:
869:
820:i := lo
761:
757:
753:
733:
729:
725:
721:
717:
713:
709:
692:
655:quicksort are:
627:
619:
610:
595:
548:
477:
452:
448:
440:
437:
436:
409:
392:
389:
388:
359:comparison sort
357:Quicksort is a
334:Quicksort is a
268:
265:
264:
263:
238:
235:
234:
189:
186:
185:
148:
145:
144:
142:
108:
105:
104:
73:
69:
61:
58:
57:
34:
17:
12:
11:
5:
8572:
8562:
8561:
8556:
8551:
8534:
8533:
8531:
8530:
8525:
8520:
8514:
8512:
8508:
8507:
8505:
8504:
8502:Spaghetti sort
8499:
8494:
8493:
8492:
8481:
8479:
8475:
8474:
8472:
8471:
8466:
8461:
8456:
8451:
8446:
8440:
8438:
8432:
8431:
8429:
8428:
8423:
8418:
8413:
8411:Bitonic sorter
8407:
8405:
8401:
8400:
8398:
8397:
8392:
8387:
8382:
8377:
8372:
8367:
8362:
8357:
8352:
8346:
8344:
8340:
8339:
8337:
8336:
8331:
8326:
8321:
8315:
8313:
8309:
8308:
8306:
8305:
8300:
8295:
8290:
8285:
8280:
8278:Insertion sort
8274:
8272:
8268:
8267:
8265:
8264:
8262:Weak-heap sort
8259:
8254:
8249:
8244:
8239:
8234:
8232:Selection sort
8228:
8226:
8220:
8219:
8217:
8216:
8211:
8206:
8201:
8196:
8191:
8186:
8180:
8178:
8177:Exchange sorts
8174:
8173:
8171:
8170:
8165:
8160:
8155:
8150:
8145:
8140:
8135:
8130:
8125:
8120:
8115:
8113:Big O notation
8110:
8104:
8102:
8098:
8097:
8090:
8089:
8082:
8075:
8067:
8061:
8060:
8054:
8048:
8039:
8019:
7996:
7995:External links
7993:
7992:
7991:
7970:10.1.1.14.8162
7952:
7939:10.1.1.17.4954
7932:(3): 683–705.
7920:
7906:
7881:Clifford Stein
7866:
7844:
7834:(8): 983–993.
7816:
7778:
7768:(7): 321–322.
7752:
7718:
7691:
7655:
7652:
7650:
7649:
7632:
7611:
7579:
7566:
7548:(6): 381–396,
7532:
7508:
7483:
7462:
7436:
7429:
7403:
7378:
7345:
7323:
7304:
7289:
7275:
7239:
7222:
7216:10.1.1.57.9071
7197:
7190:
7170:
7151:
7134:
7109:10.1.1.27.1788
7081:
7038:
7027:
7009:
7002:
6976:
6961:
6931:
6887:
6870:
6863:
6821:
6803:
6784:(4): 341–344.
6761:
6731:
6724:
6703:
6654:
6632:10.1.1.14.8162
6592:
6578:
6541:
6520:
6513:
6490:
6455:
6428:
6426:
6423:
6422:
6421:
6414:
6413:
6397:
6394:
6369:
6366:
6363:
6360:
6357:
6353:
6332:
6329:
6326:
6321:
6317:
6313:
6310:
6306:
6285:
6282:
6279:
6276:
6273:
6270:
6266:
6245:
6242:
6239:
6235:
6231:
6228:
6225:
6222:
6219:
6204:
6203:Generalization
6201:
6189:Main article:
6186:
6183:
6150:
6149:BlockQuicksort
6147:
6009:
6006:
5937:Main article:
5934:
5931:
5918:
5913:
5909:
5905:
5902:
5882:
5859:
5856:
5853:
5850:
5845:
5842:
5839:
5836:
5833:
5830:
5827:
5824:
5821:
5798:
5795:
5792:
5789:
5786:
5781:
5777:
5773:
5770:
5749:
5729:
5709:
5689:
5669:
5649:
5629:
5609:
5589:
5569:
5549:
5529:
5509:
5489:
5469:
5449:
5429:
5409:
5406:
5402:
5398:
5395:
5392:
5372:
5369:
5349:
5346:
5333:
5330:
5324:is done using
5291:
5288:
5286:
5283:
5180:
5177:
5085:performance.
5020:
5017:
4901:
4900:
4882:tail recursion
4867:
4838:
4835:
4834:
4833:
4822:
4819:
4816:
4813:
4810:
4807:
4804:
4801:
4798:
4794:
4790:
4787:
4784:
4779:
4775:
4770:
4766:
4763:
4757:
4754:
4751:
4747:
4740:
4737:
4734:
4730:
4724:
4720:
4716:
4713:
4710:
4707:
4704:
4701:
4672:
4669:
4666:
4662:
4638:
4634:
4611:
4607:
4586:
4581:
4577:
4573:
4568:
4564:
4560:
4557:
4554:
4549:
4545:
4541:
4536:
4532:
4528:
4508:
4503:
4499:
4495:
4492:
4489:
4484:
4480:
4476:
4471:
4467:
4463:
4438:
4434:
4411:
4407:
4384:
4380:
4357:
4353:
4322:
4318:
4314:
4311:
4308:
4303:
4299:
4295:
4290:
4286:
4247:
4242:
4239:
4236:
4232:
4228:
4225:
4220:
4217:
4214:
4210:
4204:
4200:
4196:
4193:
4190:
4187:
4184:
4181:
4157:
4154:
4151:
4148:
4145:
4116:
4112:
4089:
4085:
4062:
4059:
4056:
4052:
4029:
4026:
4023:
4019:
4013:
4010:
4007:
4003:
3997:
3993:
3989:
3986:
3962:
3957:
3953:
3949:
3946:
3943:
3938:
3934:
3930:
3925:
3921:
3917:
3894:
3889:
3885:
3881:
3878:
3875:
3870:
3866:
3862:
3857:
3853:
3849:
3836:The following
3833:
3830:
3820:
3813:
3801:
3773:
3756:
3732:
3731:
3716:
3713:
3710:
3707:
3704:
3701:
3697:
3691:
3688:
3681:
3676:
3672:
3668:
3665:
3660:
3657:
3650:
3647:
3644:
3639:
3636:
3633:
3629:
3625:
3622:
3616:
3613:
3610:
3606:
3599:
3594:
3591:
3588:
3584:
3580:
3575:
3571:
3568:
3565:
3562:
3556:
3553:
3551:
3549:
3546:
3537:
3535:
3529:
3526:
3523:
3519:
3514:
3509:
3506:
3501:
3495:
3492:
3489:
3484:
3481:
3478:
3475:
3472:
3469:
3463:
3457:
3454:
3451:
3447:
3442:
3436:
3433:
3430:
3427:
3424:
3421:
3417:
3412:
3407:
3404:
3399:
3393:
3390:
3387:
3382:
3379:
3376:
3373:
3370:
3367:
3361:
3358:
3356:
3354:
3348:
3345:
3342:
3338:
3333:
3328:
3324:
3321:
3318:
3315:
3312:
3309:
3303:
3297:
3294:
3291:
3288:
3285:
3282:
3278:
3273:
3267:
3264:
3261:
3257:
3252:
3247:
3243:
3240:
3237:
3234:
3231:
3228:
3222:
3219:
3217:
3212:
3209:
3206:
3201:
3198:
3195:
3192:
3186:
3185:
3174:
3173:
3162:
3159:
3156:
3153:
3150:
3147:
3144:
3141:
3138:
3135:
3132:
3129:
3126:
3123:
3120:
3117:
3114:
3111:
3108:
3105:
3102:
3099:
3088:
3087:
3076:
3073:
3070:
3067:
3064:
3061:
3058:
3055:
3052:
3049:
3046:
3043:
3040:
3037:
3034:
3031:
3028:
3025:
3022:
3019:
3016:
3013:
3010:
3007:
3004:
3001:
2998:
2995:
2992:
2989:
2986:
2983:
2980:
2977:
2974:
2971:
2968:
2965:
2962:
2959:
2956:
2953:
2950:
2939:
2938:
2927:
2924:
2921:
2918:
2913:
2910:
2907:
2902:
2899:
2896:
2892:
2888:
2885:
2882:
2879:
2876:
2873:
2870:
2867:
2864:
2861:
2858:
2855:
2852:
2849:
2839:
2828:
2825:
2822:
2819:
2814:
2811:
2808:
2803:
2800:
2797:
2793:
2787:
2784:
2779:
2776:
2773:
2770:
2767:
2764:
2761:
2758:
2755:
2752:
2749:
2746:
2743:
2740:
2737:
2734:
2731:
2728:
2725:
2722:
2717:
2714:
2711:
2706:
2703:
2700:
2696:
2690:
2687:
2682:
2679:
2676:
2673:
2670:
2667:
2664:
2661:
2658:
2568:tells us that
2562:
2561:
2550:
2546:
2541:
2538:
2533:
2529:
2526:
2523:
2520:
2517:
2514:
2511:
2508:
2505:
2502:
2499:
2496:
2442:selection sort
2438:insertion sort
2434:
2433:
2422:
2419:
2416:
2413:
2410:
2407:
2404:
2401:
2398:
2395:
2392:
2389:
2386:
2383:
2380:
2377:
2374:
2371:
2368:
2365:
2362:
2359:
2356:
2353:
2350:
2347:
2344:
2341:
2338:
2335:
2332:
2329:
2326:
2323:
2267:
2264:
2221:
2218:
2213:
2209:
2205:
2201:
2197:
2132:
2129:
2124:
2120:
2116:
2112:
2095:
2092:
2073:elements with
2040:
2037:
1980:
1966:
1959:
1956:
1931:
1926:
1922:
1918:
1915:
1912:
1909:
1906:
1903:
1900:
1897:
1892:
1887:
1884:
1881:
1877:
1816:
1813:
1811:
1808:
1687:
1684:
1683:
1682:
1679:cache memories
1648:
1645:insertion sort
1641:
1614:
1611:
1486:// Pivot value
1452:
1448:Version 7 Unix
1430:quadratic time
1424:
1421:
1386:
1385:
1343:), Mo3(middle
1295:
1273:elements (see
1242:
1225:
1222:
1220:
1217:
983:// Right index
972:// Pivot value
942:
880:
877:
838:A <= pivot
766:
746:insertion sort
702:in their book
691:
688:
683:
682:
675:
668:
661:
639:already sorted
618:
615:
501:insertion sort
476:
473:
460:
455:
451:
447:
444:
431:items. In the
416:
412:
408:
405:
402:
399:
396:
308:
307:
304:
300:
299:
287:
284:
281:
278:
275:
272:
251:
248:
245:
242:
232:
223:
222:
211:
208:
205:
202:
199:
196:
193:
183:
174:
173:
161:
158:
155:
152:
130:
127:
124:
121:
118:
115:
112:
102:
93:
92:
81:
76:
72:
68:
65:
55:
46:
45:
40:
36:
35:
32:
15:
9:
6:
4:
3:
2:
8571:
8560:
8557:
8555:
8552:
8550:
8547:
8546:
8544:
8529:
8526:
8524:
8521:
8519:
8516:
8515:
8513:
8509:
8503:
8500:
8498:
8495:
8491:
8488:
8487:
8486:
8483:
8482:
8480:
8476:
8470:
8467:
8465:
8462:
8460:
8457:
8455:
8452:
8450:
8447:
8445:
8442:
8441:
8439:
8437:
8433:
8427:
8424:
8422:
8419:
8417:
8414:
8412:
8409:
8408:
8406:
8402:
8396:
8393:
8391:
8388:
8386:
8383:
8381:
8378:
8376:
8373:
8371:
8370:Counting sort
8368:
8366:
8363:
8361:
8358:
8356:
8353:
8351:
8348:
8347:
8345:
8341:
8335:
8332:
8330:
8327:
8325:
8322:
8320:
8317:
8316:
8314:
8310:
8304:
8301:
8299:
8296:
8294:
8291:
8289:
8286:
8284:
8281:
8279:
8276:
8275:
8273:
8269:
8263:
8260:
8258:
8255:
8253:
8250:
8248:
8245:
8243:
8240:
8238:
8235:
8233:
8230:
8229:
8227:
8225:
8221:
8215:
8212:
8210:
8207:
8205:
8202:
8200:
8197:
8195:
8194:Odd–even sort
8192:
8190:
8187:
8185:
8182:
8181:
8179:
8175:
8169:
8166:
8164:
8161:
8159:
8158:X + Y sorting
8156:
8154:
8151:
8149:
8146:
8144:
8143:Adaptive sort
8141:
8139:
8136:
8134:
8131:
8129:
8126:
8124:
8121:
8119:
8116:
8114:
8111:
8109:
8106:
8105:
8103:
8099:
8095:
8088:
8083:
8081:
8076:
8074:
8069:
8068:
8065:
8058:
8055:
8052:
8049:
8047:
8043:
8040:
8028:
8024:
8020:
8007:
8003:
7999:
7998:
7988:
7984:
7980:
7976:
7971:
7966:
7962:
7958:
7953:
7949:
7945:
7940:
7935:
7931:
7928:
7927:
7921:
7918:
7914:
7910:
7907:
7904:
7903:0-262-03293-7
7900:
7896:
7892:
7888:
7887:
7882:
7878:
7874:
7870:
7867:
7864:
7863:0-201-89685-0
7860:
7856:
7852:
7848:
7845:
7841:
7837:
7833:
7829:
7825:
7821:
7817:
7814:
7813:
7805:
7800:
7796:
7793:
7792:
7787:
7783:
7779:
7775:
7771:
7767:
7763:
7762:
7757:
7753:
7749:
7745:
7741:
7737:
7733:
7729:
7728:
7723:
7719:
7714:
7709:
7705:
7701:
7697:
7692:
7688:
7684:
7680:
7676:
7672:
7668:
7667:
7662:
7661:Sedgewick, R.
7658:
7657:
7646:
7642:
7636:
7627:
7622:
7615:
7607:
7603:
7599:
7592:
7591:
7583:
7576:
7570:
7563:
7559:
7555:
7551:
7547:
7543:
7536:
7528:
7521:
7520:
7512:
7503:
7498:
7494:
7487:
7478:
7473:
7466:
7450:
7446:
7440:
7432:
7426:
7422:
7418:
7414:
7407:
7396:
7389:
7382:
7374:
7370:
7365:
7360:
7356:
7349:
7341:
7337:
7330:
7328:
7319:
7315:
7308:
7300:
7293:
7286:
7284:
7278:
7272:
7268:
7264:
7259:
7254:
7250:
7243:
7226:
7217:
7212:
7208:
7201:
7193:
7187:
7183:
7182:
7174:
7166:
7162:
7155:
7148:
7144:
7138:
7131:
7127:
7123:
7119:
7115:
7110:
7105:
7102:(1): 66–104.
7101:
7097:
7090:
7088:
7086:
7077:
7073:
7069:
7065:
7061:
7057:
7056:
7051:
7050:Sedgewick, R.
7045:
7043:
7036:
7031:
7025:
7022:
7019:
7013:
7005:
6999:
6995:
6994:
6989:
6983:
6981:
6972:
6968:
6964:
6958:
6954:
6950:
6946:
6942:
6935:
6927:
6923:
6918:
6913:
6909:
6905:
6901:
6897:
6891:
6883:
6882:
6874:
6866:
6864:0-262-03384-4
6860:
6856:
6855:
6850:
6846:
6842:
6838:
6832:
6830:
6828:
6826:
6817:
6810:
6808:
6799:
6795:
6791:
6787:
6783:
6779:
6772:
6765:
6750:
6746:
6740:
6738:
6736:
6727:
6721:
6717:
6713:
6707:
6699:
6695:
6691:
6687:
6682:
6677:
6673:
6669:
6665:
6658:
6650:
6646:
6642:
6638:
6633:
6628:
6624:
6620:
6616:
6609:
6607:
6605:
6603:
6601:
6599:
6597:
6588:
6582:
6574:
6570:
6566:
6562:
6558:
6554:
6553:
6545:
6538:
6534:
6530:
6527:C.L. Foster,
6524:
6516:
6510:
6506:
6505:
6500:
6494:
6486:
6482:
6478:
6474:
6473:
6468:
6462:
6460:
6443:
6439:
6433:
6429:
6419:
6416:
6415:
6411:
6405:
6400:
6393:
6391:
6387:
6383:
6364:
6361:
6358:
6351:
6327:
6324:
6319:
6315:
6311:
6280:
6277:
6274:
6271:
6240:
6233:
6229:
6226:
6223:
6220:
6217:
6209:
6200:
6192:
6182:
6180:
6176:
6171:
6169:
6165:
6161:
6157:
6146:
6143:
6139:
6136:uniqueprefix(
6131:
6127:
6120:
6116:
6109:
6105:
6099:
6095:
6090:
6084:
6080:
6069:
6065:
6056:
6052:
6039:
6035:
6030:
6026:
6020:
6016:
6005:
6003:
5999:
5989:
5982:
5978:
5971:
5967:
5960:
5956:
5946:
5940:
5930:
5911:
5907:
5900:
5880:
5854:
5851:
5840:
5837:
5834:
5828:
5825:
5822:
5819:
5790:
5784:
5779:
5775:
5768:
5747:
5727:
5707:
5687:
5667:
5647:
5627:
5607:
5587:
5567:
5547:
5527:
5507:
5487:
5467:
5447:
5427:
5407:
5404:
5400:
5396:
5393:
5390:
5370:
5367:
5347:
5344:
5329:
5327:
5323:
5319:
5315:
5309:
5302:
5282:
5277:
5273:
5269:
5262:
5258:
5252:
5248:
5244:
5240:
5233:
5229:
5224:
5219:
5215:
5211:
5204:
5200:
5195:
5186:
5176:
5174:
5170:
5168:
5164:
5160:
5155:
5151:
5146:
5142:
5135:
5131:
5124:
5120:
5115:
5109:
5105:
5101:
5096:
5091:
5088:
5082:
5078:
5073:
5069:
5063:
5059:
5055:
5050:
5045:
5040:
5036:
5032:buffers, and
5030:
5026:
5016:
5011:
5007:
5001:
4997:
4993:
4989:
4982:
4978:
4967:
4963:
4958:
4954:
4949:
4945:
4941:
4934:
4930:
4923:
4919:
4912:
4908:
4896:
4892:
4887:
4883:
4877:
4873:
4868:
4863:
4858:
4857:
4856:
4852:
4848:
4842:
4820:
4814:
4811:
4808:
4805:
4799:
4796:
4792:
4788:
4785:
4782:
4777:
4773:
4768:
4764:
4761:
4755:
4752:
4749:
4745:
4738:
4735:
4732:
4728:
4722:
4718:
4714:
4708:
4702:
4692:
4691:
4690:
4687:
4670:
4667:
4664:
4660:
4636:
4632:
4609:
4605:
4579:
4575:
4571:
4566:
4562:
4558:
4555:
4552:
4547:
4543:
4539:
4534:
4530:
4501:
4497:
4493:
4490:
4487:
4482:
4478:
4474:
4469:
4465:
4452:
4436:
4432:
4409:
4405:
4382:
4378:
4355:
4351:
4340:
4320:
4316:
4312:
4309:
4306:
4301:
4297:
4293:
4288:
4284:
4275:. The values
4273:
4269:
4259:
4240:
4237:
4234:
4230:
4218:
4215:
4212:
4208:
4202:
4198:
4194:
4188:
4182:
4152:
4146:
4135:
4130:
4114:
4110:
4087:
4083:
4060:
4057:
4054:
4050:
4027:
4024:
4021:
4017:
4011:
4008:
4005:
4001:
3995:
3991:
3987:
3984:
3955:
3951:
3947:
3944:
3941:
3936:
3932:
3928:
3923:
3919:
3906:
3887:
3883:
3879:
3876:
3873:
3868:
3864:
3860:
3855:
3851:
3839:
3829:
3825:
3818:
3811:
3807:
3797:
3789:
3779:
3769:
3764:
3761:
3754:
3750:
3746:
3742:
3738:
3714:
3711:
3708:
3705:
3702:
3699:
3689:
3686:
3679:
3674:
3670:
3666:
3663:
3658:
3655:
3648:
3645:
3642:
3637:
3634:
3631:
3627:
3623:
3620:
3614:
3611:
3608:
3604:
3597:
3592:
3589:
3586:
3582:
3578:
3573:
3566:
3560:
3554:
3552:
3544:
3527:
3524:
3521:
3517:
3512:
3507:
3504:
3499:
3493:
3490:
3487:
3479:
3476:
3473:
3467:
3461:
3455:
3452:
3449:
3445:
3440:
3434:
3428:
3425:
3422:
3415:
3410:
3405:
3402:
3397:
3391:
3388:
3385:
3377:
3374:
3371:
3365:
3359:
3357:
3346:
3343:
3340:
3336:
3331:
3326:
3319:
3316:
3313:
3307:
3301:
3292:
3289:
3286:
3280:
3276:
3271:
3265:
3262:
3259:
3255:
3250:
3245:
3238:
3235:
3232:
3226:
3220:
3218:
3210:
3207:
3204:
3196:
3190:
3176:
3175:
3160:
3157:
3154:
3151:
3148:
3142:
3139:
3136:
3130:
3124:
3121:
3118:
3112:
3106:
3100:
3097:
3090:
3089:
3071:
3068:
3065:
3059:
3056:
3053:
3047:
3044:
3041:
3032:
3029:
3026:
3020:
3014:
3011:
3008:
3002:
2999:
2993:
2990:
2987:
2981:
2975:
2972:
2969:
2963:
2957:
2951:
2948:
2941:
2940:
2922:
2916:
2911:
2908:
2905:
2900:
2897:
2894:
2890:
2886:
2883:
2877:
2874:
2871:
2865:
2862:
2856:
2850:
2847:
2840:
2823:
2817:
2812:
2809:
2806:
2801:
2798:
2795:
2791:
2785:
2782:
2777:
2774:
2771:
2768:
2765:
2756:
2753:
2750:
2747:
2744:
2738:
2735:
2729:
2723:
2715:
2712:
2709:
2704:
2701:
2698:
2694:
2688:
2685:
2680:
2677:
2674:
2671:
2668:
2662:
2656:
2649:
2648:
2647:
2643:
2636:
2629:
2625:
2614:
2606:
2602:
2598:
2592:
2588:
2584:
2580:
2576:
2572:
2567:
2548:
2544:
2539:
2536:
2531:
2527:
2524:
2521:
2515:
2509:
2506:
2500:
2494:
2487:
2486:
2485:
2481:
2474:
2470:
2464:
2460:
2456:
2452:
2448:
2443:
2439:
2420:
2414:
2411:
2408:
2402:
2399:
2393:
2387:
2384:
2378:
2375:
2372:
2366:
2363:
2357:
2351:
2348:
2342:
2336:
2333:
2327:
2321:
2314:
2313:
2312:
2308:
2297:
2293:
2282:
2278:
2273:
2263:
2259:
2255:
2251:
2240:
2236:
2219:
2216:
2211:
2207:
2203:
2199:
2195:
2187:
2182:
2171:
2159:
2155:
2151:
2147:
2130:
2127:
2122:
2118:
2114:
2110:
2101:
2091:
2088:
2086:
2085:
2080:
2076:
2066:
2059:
2055:
2051:
2036:
2032:
2028:
2024:
2017:
2013:
2006:
2002:
1995:
1991:
1985:
1976:
1971:
1955:
1951:
1947:
1924:
1920:
1913:
1910:
1904:
1901:
1898:
1890:
1885:
1882:
1879:
1875:
1863:
1859:
1855:
1851:th call does
1844:
1839:
1833:
1827:
1823:
1807:
1801:
1797:
1791:
1787:
1782:
1778:
1773:
1771:
1766:
1762:
1754:
1746:
1742:
1730:
1722:
1718:
1711:
1701:
1697:
1693:
1680:
1670:
1666:
1649:
1646:
1642:
1639:
1635:
1629:
1625:
1620:
1619:
1618:
1613:Optimizations
1610:
1603:
1599:
1593:
1579:
1576:
1572:
1569:
1568:
1564:
1559:
1555:
1551:
1547:
1544:
1541:
1538:A > pivot
1537:
1534:
1530:
1526:
1522:
1518:
1515:
1512:
1509:A < pivot
1508:
1505:
1501:
1498:
1494:
1491:
1487:
1484:
1480:
1477:
1473:
1469:
1465:
1462:
1458:
1455:
1451:
1449:
1444:
1439:
1434:
1431:
1420:
1416:
1412:
1408:
1401:
1397:
1391:
1382:
1363:), Mo3(final
1362:
1342:
1322:
1317:
1316:
1315:
1313:
1308:
1304:
1298:
1294:
1293:
1286:
1282:
1276:
1267:
1254:
1250:
1246:
1241:
1238:
1236:
1232:
1216:
1214:
1211:
1207:
1194:
1192:
1186:
1183:
1171:
1164:
1152:
1150:
1146:
1142:
1138:
1118:
1115:
1112:
1108:
1101:
1100:
1096:
1076:
1072:
1068:
1060:
1056:
1049:
1040:
1036:
1033:
1029:
1026:
1022:
1019:
1015:
1011:
1008:
1005:
1001:
997:
994:
991:
988:
984:
980:
979:// Left index
977:
973:
970:
966:
963:
959:
955:
952:
948:
945:
941:
939:
934:
930:
926:
920:
916:
909:
906:
885:
876:
868:
864:
860:
856:
852:
848:
844:
841:
837:
834:
831:
827:
824:j := lo
823:
819:
816:
812:
808:
805:
802:
798:
794:
790:
786:
782:
779:
776:
772:
769:
765:
751:
747:
740:
736:
707:
706:
701:
697:
687:
679:
676:
672:
669:
666:
662:
658:
657:
656:
654:
649:
640:
634:
630:
623:
614:
608:
607:AntiQuicksort
602:
598:
593:
592:
587:
583:
578:
574:
570:
566:
562:
558:
556:
551:
546:
542:
537:
535:
531:
530:
525:
521:
518:
514:
510:
506:
502:
498:
497:magnetic tape
494:
490:
486:
482:
472:
471:comparisons.
453:
449:
442:
434:
430:
410:
406:
403:
400:
394:
386:
382:
378:
376:
372:
368:
364:
360:
355:
353:
349:
345:
341:
337:
332:
330:
326:
322:
318:
314:
305:
301:
282:
279:
276:
270:
246:
240:
233:
231:
228:
224:
206:
203:
200:
197:
191:
184:
182:
179:
175:
156:
150:
125:
122:
119:
116:
110:
103:
101:
98:
94:
74:
70:
63:
56:
54:
51:
47:
44:
41:
37:
30:
25:
19:
8436:Hybrid sorts
8385:Proxmap sort
8298:Library sort
8213:
8168:Quantum sort
8031:. Retrieved
8027:the original
8010:. Retrieved
8006:the original
7960:
7956:
7929:
7924:
7909:Faron Moller
7884:
7854:
7853:, Volume 3:
7850:
7847:Donald Knuth
7831:
7827:
7811:
7797:(1): 10–16.
7794:
7789:
7765:
7759:
7731:
7725:
7703:
7699:
7670:
7664:
7644:
7635:
7614:
7589:
7582:
7569:
7545:
7541:
7535:
7518:
7511:
7492:
7486:
7465:
7453:. Retrieved
7448:
7439:
7412:
7406:
7395:the original
7381:
7354:
7348:
7339:
7307:
7292:
7282:
7280:
7248:
7242:
7225:
7206:
7200:
7180:
7173:
7164:
7154:
7146:
7137:
7129:
7099:
7095:
7059:
7053:
7030:
7012:
6992:
6944:
6934:
6910:(1): 10–16.
6907:
6903:
6890:
6880:
6873:
6853:
6815:
6781:
6777:
6764:
6752:. Retrieved
6748:
6715:
6712:Bentley, Jon
6706:
6671:
6667:
6657:
6622:
6618:
6581:
6559:(3): 38–41.
6556:
6550:
6544:
6528:
6523:
6503:
6493:
6476:
6470:
6446:. Retrieved
6442:the original
6432:
6208:Richard Cole
6206:
6194:
6172:
6152:
6141:
6137:
6129:
6125:
6118:
6114:
6107:
6103:
6097:
6093:
6082:
6078:
6067:
6063:
6037:
6033:
6018:
6014:
6011:
6001:
5987:
5980:
5976:
5974:or at least
5969:
5965:
5958:
5954:
5942:
5335:
5307:
5300:
5293:
5275:
5271:
5267:
5260:
5256:
5253:
5246:
5242:
5238:
5231:
5227:
5220:
5213:
5209:
5202:
5198:
5187:chooses the
5182:
5171:
5163:disk storage
5153:
5150:linked lists
5147:
5140:
5133:
5129:
5122:
5118:
5107:
5103:
5099:
5092:
5080:
5076:
5067:
5061:
5057:
5053:
5046:
5038:
5034:
5022:
5009:
5005:
5002:
4995:
4991:
4987:
4980:
4976:
4965:
4961:
4956:
4952:
4950:
4943:
4939:
4932:
4928:
4921:
4917:
4910:
4906:
4902:
4894:
4890:
4886:R. Sedgewick
4875:
4871:
4861:
4850:
4846:
4843:
4840:
4688:
4453:
4338:
4271:
4267:
4260:
4131:
3907:
3835:
3823:
3816:
3809:
3805:
3777:
3765:
3759:
3752:
3748:
3744:
3740:
3736:
3733:
2641:
2634:
2627:
2623:
2612:
2604:
2600:
2596:
2593:
2586:
2582:
2578:
2574:
2570:
2563:
2479:
2472:
2468:
2465:
2458:
2454:
2450:
2446:
2435:
2306:
2295:
2291:
2280:
2276:
2269:
2257:
2253:
2249:
2238:
2234:
2180:
2177:heads after
2169:
2160:
2153:
2149:
2145:
2097:
2089:
2082:
2078:
2064:
2057:
2053:
2049:
2042:
2030:
2026:
2022:
2015:
2011:
2004:
2000:
1993:
1989:
1983:
1969:
1961:
1949:
1945:
1861:
1857:
1853:
1842:
1831:
1828:
1821:
1818:
1789:
1785:
1774:
1767:
1760:
1752:
1744:
1740:
1728:
1720:
1716:
1709:
1689:
1668:
1664:
1627:
1623:
1616:
1601:
1597:
1594:
1582:
1577:
1574:
1570:
1566:
1562:
1560:
1557:
1553:
1549:
1545:
1542:
1539:
1535:
1532:
1528:
1524:
1520:
1516:
1513:
1510:
1506:
1503:
1502:eq <= gt
1499:
1496:
1492:
1489:
1485:
1482:
1478:
1475:
1471:
1467:
1463:
1460:
1456:
1453:
1435:
1426:
1414:
1410:
1406:
1399:
1395:
1387:
1380:
1360:
1340:
1320:
1306:
1302:
1296:
1291:
1284:
1280:
1268:
1257:
1252:
1248:
1244:
1239:
1227:
1213:
1210:
1205:
1195:
1188:
1185:
1173:
1170:
1163:
1153:
1148:
1144:
1140:
1136:
1117:
1114:
1110:
1106:"do...while"
1104:
1102:
1098:
1097:
1074:
1070:
1066:
1058:
1054:
1050:
1043:
1038:
1034:
1031:
1027:
1024:
1020:
1017:
1013:
1009:
1006:
1003:
999:
995:
992:
989:
987:loop forever
986:
982:
978:
975:
971:
968:
964:
961:
957:
953:
950:
946:
943:
935:
928:
924:
922:rather than
918:
914:
910:
902:
870:
866:
862:
858:
854:
850:
846:
842:
839:
835:
832:
829:
825:
821:
817:
814:
810:
806:
803:
800:
796:
792:
788:
784:
780:
777:
774:
770:
767:
738:
734:
703:
699:
695:
693:
684:
670:
664:
645:
638:
632:
628:
606:
600:
596:
589:
581:
576:
573:Doug McIlroy
559:
538:
527:
478:
428:
379:
370:
366:
356:
339:
333:
312:
311:
18:
8518:Stooge sort
8360:Bucket sort
8312:Merge sorts
8184:Bubble sort
8128:Inplacement
8118:Total order
8033:25 November
8012:25 November
7895:McGraw-Hill
7786:"Quicksort"
7455:4 September
7016:qsort.c in
6900:"Quicksort"
6668:Commun. ACM
5194:quickselect
5173:Bucket sort
5114:stable sort
4651:is exactly
2158:algorithm.
1757:time using
1198:(lo..p - 1)
1129:(lo..p - 1)
698:and Cormen
678:Recursively
586:Nico Lomuto
569:Jon Bentley
547:subroutine
435:, it makes
363:total order
344:recursively
181:performance
100:performance
53:performance
8543:Categories
8464:Spreadsort
8426:Samplesort
8390:Radix sort
8319:Merge sort
8257:Cycle sort
8242:Smoothsort
8204:Gnome sort
7791:Comput. J.
7734:(7): 321.
7654:References
7626:1604.06697
7477:1511.01138
7258:1811.99833
7165:Dr. Dobb's
6537:0122626605
6479:(7): 321.
6168:data cache
6029:radix sort
5945:radix sort
5318:primitives
5097:, another
5095:merge sort
3786:items (as
2100:percentile
1794:time on a
1781:radix sort
1770:merge sort
1565:A = pivot
1023:i >= j
938:pseudocode
905:Tony Hoare
750:pseudocode
565:Samplesort
481:Tony Hoare
433:worst case
385:on average
325:merge sort
321:Tony Hoare
227:Worst-case
50:Worst-case
8459:Introsort
8395:Flashsort
8365:Burstsort
8355:Bead sort
8293:Tree sort
8288:Splaysort
8283:Shellsort
8214:Quicksort
8199:Comb sort
8133:Stability
8046:Pat Morin
7965:CiteSeerX
7934:CiteSeerX
7891:MIT Press
7761:Comm. ACM
7727:Comm. ACM
7666:Comm. ACM
7364:1310.7409
7211:CiteSeerX
7126:206567217
7104:CiteSeerX
7055:Comm. ACM
6926:0010-4620
6690:0001-0782
6627:CiteSeerX
6552:Comm. ACM
6472:Comm. ACM
6418:Introsort
6382:Sedgewick
6362:
6325:
6305:Θ
6278:
6265:Θ
6224:
6023:parallel
5829:
5785:
5087:Introsort
4812:
4786:
4774:∑
4729:∑
4719:∑
4703:
4556:…
4491:…
4310:…
4209:∑
4199:∑
4183:
4147:
4002:∑
3992:∑
3945:…
3877:…
3712:
3671:∫
3664:≈
3646:−
3628:∑
3621:≤
3583:∑
3545:⋮
3491:−
3477:−
3462:≤
3426:−
3411:−
3389:−
3375:−
3317:−
3302:≤
3272:−
3236:−
3158:−
3140:−
3069:−
3045:−
3030:−
3021:−
3012:−
2991:−
2973:−
2964:−
2909:−
2891:∑
2875:−
2810:−
2792:∑
2772:−
2754:−
2748:−
2713:−
2695:∑
2675:−
2412:−
2376:−
2217:
2128:
1975:call tree
1902:−
1876:∑
1838:call tree
1638:tail call
1607:partition
1590:quicksort
1585:partition
1479:algorithm
1457:algorithm
1235:Sedgewick
1180:(p+1..hi)
1160:(p+1..hi)
1125:(p+1..hi)
1093:(p+1..hi)
1089:(lo..p-1)
1085:(p+1..hi)
965:algorithm
947:algorithm
807:algorithm
787:return
771:algorithm
671:Partition
617:Algorithm
509:Shellsort
407:
313:Quicksort
280:
204:
123:
97:Best-case
22:Quicksort
8528:Bogosort
8523:Slowsort
8237:Heapsort
7897:, 2001.
7822:(1997).
7815:, 1989.)
7784:(1962).
7748:52800011
7687:10020756
7451:. Oracle
7445:"Arrays"
7318:Archived
7076:10020756
7018:GNU libc
6798:35935409
6754:3 August
6531:, 1992,
6501:(2008).
6448:22 April
6396:See also
6140:) ≫ log
6072:, as if
5285:Variants
5049:heapsort
4042:, where
2274:for the
1749:work in
1714:work in
1552:A
1523:A
1319:ninther(
1301:≈ 1.188
849:A
756:through
728:through
720:through
660:skipped.
653:in-place
513:sixpence
505:Autocode
348:in-place
329:heapsort
8454:Timsort
7987:8822797
7706:: 1–5.
7562:6829805
7369:Bibcode
7149:. 2013.
6971:7830071
6698:4774719
6649:8822797
6573:1868477
6539:, p. 98
6390:McIlroy
6386:Bentley
6179:pdqsort
6002:exactly
5326:Timsort
5322:objects
5068:average
3798:yields
3751:≈ 1.39
1580:lt, gt
1377:
1365:
1357:
1345:
1337:
1325:
1312:ninther
1202:(p..hi)
1190:(lo..p)
1176:(lo..p)
1167:(lo..p)
1156:(lo..p)
1149:ceiling
1133:(p..hi)
1121:(lo..p)
1081:(lo..p)
857:swap A
845:swap A
828:hi - 1
475:History
303:Optimal
178:Average
8101:Theory
7985:
7967:
7936:
7901:
7879:, and
7861:
7746:
7685:
7598:Zurich
7560:
7427:
7273:
7213:
7188:
7124:
7106:
7074:
7000:
6969:
6959:
6924:
6861:
6796:
6722:
6696:
6688:
6647:
6629:
6571:
6535:
6511:
6164:blocks
6096:≫ log
6091:. If
5992:, and
5314:Java 7
4979:((log
4866:space.
3743:) = 2
3542:
3539:
2079:et al.
2035:time.
1954:time.
1751:O(log
1694:using
1578:return
1279:1.386
1231:median
1030:j
1028:return
925:repeat
863:return
700:et al.
611:aqsort
375:stable
352:memory
8478:Other
8123:Lists
7983:S2CID
7744:S2CID
7683:S2CID
7621:arXiv
7594:(PDF)
7558:S2CID
7523:(PDF)
7472:arXiv
7398:(PDF)
7391:(PDF)
7359:arXiv
7253:arXiv
7122:S2CID
7072:S2CID
6967:S2CID
6794:S2CID
6774:(PDF)
6694:S2CID
6645:S2CID
6569:S2CID
6425:Notes
6106:(log
6066:(log
6057:with
5990:<2
5132:(log
5037:(log
4964:(log
4920:(log
4909:(log
4893:(log
4874:(log
4849:(log
3819:− log
3808:!) ≈
2237:(log
1788:(log
1719:(log
1634:recur
1626:(log
1500:while
1443:qsort
1147:v.s.
1145:floor
1127:, or
1014:while
1000:while
929:until
919:while
897:pivot
665:pivot
637:) on
550:qsort
524:ALGOL
39:Class
8035:2008
8014:2008
7899:ISBN
7893:and
7859:ISBN
7457:2014
7425:ISBN
7271:ISBN
7186:ISBN
6998:ISBN
6957:ISBN
6922:ISSN
6859:ISBN
6756:2015
6720:ISBN
6686:ISSN
6533:ISBN
6509:ISBN
6450:2015
6384:and
6175:LLVM
6042:for
6025:PRAM
5520:and
5480:and
5274:log
5245:log
5106:log
5060:log
4994:log
4955:and
4736:<
4270:<
4265:and
4261:Fix
4216:<
4009:<
3812:(log
2621:and
2603:log
2585:log
2577:) =
2564:The
2453:) =
2440:and
2304:and
2256:log
2152:log
2056:log
2029:log
1800:PRAM
1796:CRCW
1743:log
1583:The
1567:then
1558:else
1550:with
1546:swap
1540:then
1533:else
1521:with
1517:swap
1511:then
1468:then
1305:log
1283:log
1200:and
1178:and
1158:and
1131:and
1123:and
1091:and
1073:log(
1039:with
1035:swap
1025:then
958:then
891:and
861:A
859:with
847:with
840:then
785:then
571:and
555:Java
541:Unix
369:and
327:and
7975:doi
7944:doi
7836:doi
7799:doi
7770:doi
7736:doi
7708:doi
7704:154
7675:doi
7602:doi
7550:doi
7497:doi
7417:doi
7263:doi
7114:doi
7064:doi
6949:doi
6912:doi
6786:doi
6676:doi
6637:doi
6561:doi
6481:doi
6392:).
6359:log
6316:log
6275:log
6221:log
6061:in
5776:log
5640:or
5600:or
5310:= 3
5303:− 1
5165:or
5154:can
5143:(1)
4864:(1)
4809:log
4783:log
4172:is
4168:of
4132:By
3800:log
3772:log
3755:log
3747:ln
2644:− 1
2637:− 1
2630:− 1
2615:− 1
2200:log
2179:100
2111:log
1979:log
1977:is
1965:log
1845:− 1
1834:− 1
1824:− 1
1737:in
1561://
1446:of
1417:)/2
1409:+ (
1402:)/2
1379:of
1359:of
1339:of
1299:, 2
1151:).
1139:or
936:In
927:...
917:...
822:for
722:i-1
536:.
404:log
277:log
201:log
143:or
120:log
8545::
8044:,
7981:.
7973:.
7961:23
7959:.
7942:.
7930:31
7911:.
7883:.
7875:,
7871:,
7849:.
7832:27
7830:.
7826:.
7788:.
7764:.
7742:.
7730:.
7702:.
7698:.
7681:.
7671:21
7669:.
7600:.
7556:,
7546:11
7544:,
7447:.
7423:.
7367:.
7338:.
7326:^
7316:.
7279:.
7269:.
7261:.
7163:.
7145:,
7128:.
7120:.
7112:.
7100:31
7098:.
7084:^
7070:.
7060:21
7058:.
7041:^
7023:,
7020::
6979:^
6965:.
6955:.
6943:.
6920:.
6906:.
6902:.
6847:;
6843:;
6839:;
6824:^
6806:^
6792:.
6782:29
6780:.
6776:.
6747:.
6734:^
6692:.
6684:.
6672:13
6670:.
6666:.
6643:.
6635:.
6623:23
6621:.
6617:.
6595:^
6567:.
6557:52
6555:.
6475:.
6458:^
6038:KN
5968:(2
5959:KN
5826:ln
5183:A
5169:.
4983:))
4957:hi
4953:lo
4686:.
4451:.
4341:+1
4258:.
4224:Pr
4129:.
3794:,
3780:!)
3763:.
3709:ln
2626:−
2591:.
2482:/2
2463:.
2309:−1
2081:,
1860:−
1759:O(
1739:O(
1727:O(
1708:O(
1669:kn
1600:≪
1592:.
1563:if
1548:A
1536:if
1519:A
1507:if
1504:do
1483:is
1464:if
1461:is
1415:lo
1411:hi
1407:lo
1400:hi
1398:+
1396:lo
1383:))
1253:if
1249:if
1245:if
1077:))
1048:.
1041:A
1037:A
1021:if
1010:do
996:do
969:is
954:if
951:is
940:,
915:do
899:).
875:.
865:i
836:if
830:do
826:to
811:is
781:if
775:is
758:hi
754:lo
718:lo
557:.
306:No
8086:e
8079:t
8072:v
8037:.
8016:.
7989:.
7977::
7950:.
7946::
7919:.
7842:.
7838::
7807:.
7801::
7795:5
7776:.
7772::
7766:4
7750:.
7738::
7732:4
7716:.
7710::
7689:.
7677::
7629:.
7623::
7608:.
7604::
7552::
7529:.
7505:.
7499::
7480:.
7474::
7459:.
7433:.
7419::
7375:.
7371::
7361::
7342:.
7283:n
7265::
7255::
7235:0
7231:1
7219:.
7194:.
7167:.
7116::
7078:.
7066::
7006:.
6973:.
6951::
6928:.
6914::
6908:5
6867:.
6800:.
6788::
6758:.
6728:.
6700:.
6678::
6651:.
6639::
6575:.
6563::
6517:.
6487:.
6483::
6477:4
6452:.
6388:-
6368:)
6365:n
6356:(
6352:O
6331:)
6328:n
6320:2
6312:n
6309:(
6284:)
6281:n
6272:n
6269:(
6244:)
6241:n
6238:(
6234:O
6230:+
6227:n
6218:n
6197:k
6142:N
6138:K
6132:)
6130:N
6128:(
6126:O
6121:)
6119:K
6117:(
6115:O
6110:)
6108:N
6104:O
6098:N
6094:K
6085:)
6083:N
6081:(
6079:O
6074:K
6070:)
6068:N
6064:Θ
6059:K
6047:K
6044:N
6040:)
6036:(
6034:O
6021:)
6019:K
6017:(
6015:O
5994:K
5988:N
5983:)
5981:N
5979:(
5977:O
5972:)
5970:N
5966:O
5961:)
5957:(
5955:O
5950:W
5917:)
5912:2
5908:n
5904:(
5901:O
5881:N
5858:)
5855:B
5852:4
5849:(
5844:)
5841:1
5838:+
5835:N
5832:(
5823:+
5820:1
5797:)
5794:)
5791:n
5788:(
5780:2
5772:(
5769:O
5748:Y
5728:Y
5708:Y
5688:X
5668:X
5648:Y
5628:X
5608:Y
5588:X
5568:Y
5548:X
5528:Y
5508:X
5488:Y
5468:X
5448:Y
5428:X
5408:=
5405:B
5401:/
5397:N
5394:=
5391:M
5371:=
5368:B
5348:=
5345:N
5308:s
5301:s
5296:s
5278:)
5276:n
5272:n
5270:(
5268:O
5263:)
5261:n
5259:(
5257:O
5249:)
5247:n
5243:n
5241:(
5239:O
5234:)
5232:n
5230:(
5228:O
5216:)
5214:n
5212:(
5210:O
5205:)
5203:n
5201:(
5199:O
5189:k
5141:O
5136:)
5134:n
5130:O
5125:)
5123:n
5121:(
5119:O
5110:)
5108:n
5104:n
5102:(
5100:O
5083:)
5081:n
5079:(
5077:O
5064:)
5062:n
5058:n
5056:(
5054:O
5041:)
5039:n
5035:O
5012:)
5010:n
5008:(
5006:O
4998:)
4996:n
4992:n
4990:(
4988:O
4981:n
4977:O
4972:n
4968:)
4966:n
4962:O
4946:)
4944:n
4942:(
4940:O
4935:)
4933:n
4931:(
4929:O
4924:)
4922:n
4918:O
4913:)
4911:n
4907:O
4899:.
4897:)
4895:n
4891:O
4878:)
4876:n
4872:O
4862:O
4853:)
4851:n
4847:O
4821:.
4818:)
4815:n
4806:n
4803:(
4800:O
4797:=
4793:)
4789:i
4778:i
4769:(
4765:O
4762:=
4756:1
4753:+
4750:j
4746:2
4739:i
4733:j
4723:i
4715:=
4712:]
4709:C
4706:[
4700:E
4671:1
4668:+
4665:j
4661:2
4637:j
4633:x
4610:i
4606:x
4585:)
4580:i
4576:x
4572:,
4567:j
4563:x
4559:,
4553:,
4548:2
4544:x
4540:,
4535:1
4531:x
4527:(
4507:)
4502:n
4498:x
4494:,
4488:,
4483:2
4479:x
4475:,
4470:1
4466:x
4462:(
4437:j
4433:x
4410:i
4406:x
4383:j
4379:x
4356:i
4352:x
4339:j
4321:j
4317:x
4313:,
4307:,
4302:2
4298:x
4294:,
4289:1
4285:x
4272:i
4268:j
4263:i
4246:)
4241:j
4238:,
4235:i
4231:c
4227:(
4219:i
4213:j
4203:i
4195:=
4192:]
4189:C
4186:[
4180:E
4170:C
4156:]
4153:C
4150:[
4144:E
4115:j
4111:x
4088:i
4084:x
4061:j
4058:,
4055:i
4051:c
4028:j
4025:,
4022:i
4018:c
4012:i
4006:j
3996:i
3988:=
3985:C
3975:C
3961:)
3956:n
3952:x
3948:,
3942:,
3937:2
3933:x
3929:,
3924:1
3920:x
3916:(
3893:)
3888:n
3884:x
3880:,
3874:,
3869:2
3865:x
3861:,
3856:1
3852:x
3848:(
3826:)
3824:e
3821:2
3817:n
3814:2
3810:n
3806:n
3804:(
3802:2
3792:n
3784:n
3778:n
3776:(
3774:2
3760:n
3757:2
3753:n
3749:n
3745:n
3741:n
3739:(
3737:C
3715:n
3706:2
3703:=
3700:x
3696:d
3690:x
3687:1
3680:n
3675:1
3667:2
3659:i
3656:1
3649:1
3643:n
3638:1
3635:=
3632:i
3624:2
3615:1
3612:+
3609:i
3605:2
3598:n
3593:2
3590:=
3587:i
3579:+
3574:2
3570:)
3567:1
3564:(
3561:C
3555:=
3528:1
3525:+
3522:n
3518:2
3513:+
3508:n
3505:2
3500:+
3494:1
3488:n
3483:)
3480:2
3474:n
3471:(
3468:C
3456:1
3453:+
3450:n
3446:2
3441:+
3435:n
3432:)
3429:1
3423:n
3420:(
3416:2
3406:n
3403:2
3398:+
3392:1
3386:n
3381:)
3378:2
3372:n
3369:(
3366:C
3360:=
3347:1
3344:+
3341:n
3337:2
3332:+
3327:n
3323:)
3320:1
3314:n
3311:(
3308:C
3296:)
3293:1
3290:+
3287:n
3284:(
3281:n
3277:2
3266:1
3263:+
3260:n
3256:2
3251:+
3246:n
3242:)
3239:1
3233:n
3230:(
3227:C
3221:=
3211:1
3208:+
3205:n
3200:)
3197:n
3194:(
3191:C
3161:2
3155:n
3152:2
3149:+
3146:)
3143:1
3137:n
3134:(
3131:C
3128:)
3125:1
3122:+
3119:n
3116:(
3113:=
3110:)
3107:n
3104:(
3101:C
3098:n
3075:)
3072:1
3066:n
3063:(
3060:C
3057:2
3054:+
3051:)
3048:2
3042:n
3039:(
3036:)
3033:1
3027:n
3024:(
3018:)
3015:1
3009:n
3006:(
3003:n
3000:=
2997:)
2994:1
2988:n
2985:(
2982:C
2979:)
2976:1
2970:n
2967:(
2961:)
2958:n
2955:(
2952:C
2949:n
2926:)
2923:i
2920:(
2917:C
2912:1
2906:n
2901:0
2898:=
2895:i
2887:2
2884:+
2881:)
2878:1
2872:n
2869:(
2866:n
2863:=
2860:)
2857:n
2854:(
2851:C
2848:n
2827:)
2824:i
2821:(
2818:C
2813:1
2807:n
2802:0
2799:=
2796:i
2786:n
2783:2
2778:+
2775:1
2769:n
2766:=
2763:)
2760:)
2757:1
2751:i
2745:n
2742:(
2739:C
2736:+
2733:)
2730:i
2727:(
2724:C
2721:(
2716:1
2710:n
2705:0
2702:=
2699:i
2689:n
2686:1
2681:+
2678:1
2672:n
2669:=
2666:)
2663:n
2660:(
2657:C
2642:n
2635:n
2628:i
2624:n
2619:i
2613:n
2607:)
2605:n
2601:n
2599:(
2597:O
2589:)
2587:n
2583:n
2581:(
2579:O
2575:n
2573:(
2571:T
2549:.
2545:)
2540:2
2537:n
2532:(
2528:T
2525:2
2522:+
2519:)
2516:n
2513:(
2510:O
2507:=
2504:)
2501:n
2498:(
2495:T
2480:n
2475:)
2473:n
2471:(
2469:O
2461:)
2459:n
2457:(
2455:O
2451:n
2449:(
2447:T
2421:.
2418:)
2415:1
2409:n
2406:(
2403:T
2400:+
2397:)
2394:n
2391:(
2388:O
2385:=
2382:)
2379:1
2373:n
2370:(
2367:T
2364:+
2361:)
2358:0
2355:(
2352:T
2349:+
2346:)
2343:n
2340:(
2337:O
2334:=
2331:)
2328:n
2325:(
2322:T
2307:n
2302:0
2298:)
2296:n
2294:(
2292:O
2287:n
2283:)
2281:n
2279:(
2277:T
2260:)
2258:n
2254:n
2252:(
2250:O
2245:n
2241:)
2239:n
2235:O
2220:n
2212:3
2208:/
2204:4
2196:2
2181:k
2175:k
2170:k
2168:2
2164:k
2156:)
2154:n
2150:n
2148:(
2146:O
2131:n
2123:3
2119:/
2115:4
2071:n
2067:!
2065:n
2060:)
2058:n
2054:n
2052:(
2050:O
2045:n
2033:)
2031:n
2027:n
2025:(
2023:O
2018:)
2016:n
2014:(
2012:O
2007:)
2005:n
2003:(
2001:O
1996:)
1994:n
1992:(
1990:O
1984:n
1981:2
1970:n
1967:2
1952:)
1950:n
1948:(
1946:O
1930:)
1925:2
1921:n
1917:(
1914:O
1911:=
1908:)
1905:i
1899:n
1896:(
1891:n
1886:0
1883:=
1880:i
1864:)
1862:i
1858:n
1856:(
1854:O
1849:i
1843:n
1832:n
1822:n
1804:n
1792:)
1790:n
1786:O
1763:)
1761:n
1755:)
1753:n
1747:)
1745:n
1741:n
1735:n
1731:)
1729:n
1723:)
1721:n
1717:O
1712:)
1710:n
1704:n
1675:k
1671:)
1667:(
1665:O
1660:k
1656:k
1652:k
1630:)
1628:n
1624:O
1602:n
1598:k
1413:−
1394:(
1381:a
1374:3
1371:/
1368:1
1361:a
1354:3
1351:/
1348:1
1341:a
1334:3
1331:/
1328:1
1321:a
1307:n
1303:n
1297:n
1292:C
1285:n
1281:n
1271:n
1264:A
1260:A
1209:(
1141:j
1137:i
1075:n
1071:n
1069:(
1067:O
1061:)
1059:n
1057:(
1055:O
893:j
889:i
762:A
741:)
739:n
737:(
735:O
730:j
726:i
714:j
710:i
635:)
633:n
631:(
629:O
626:(
609:(
603:)
601:n
599:(
597:O
459:)
454:2
450:n
446:(
443:O
429:n
415:)
411:n
401:n
398:(
395:O
371:b
367:a
286:)
283:n
274:(
271:O
250:)
247:n
244:(
241:O
210:)
207:n
198:n
195:(
192:O
160:)
157:n
154:(
151:O
129:)
126:n
117:n
114:(
111:O
80:)
75:2
71:n
67:(
64:O
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
