respectable on most inputs in factif the list contains large numbers of duplicates with relatively few distinct itemsas is sometimes the casethen the performance is extremely good the algorithm we have described forms the basis of the quicksort howeverby making the extra listsand doing so recursivelyit is hard to see how we have improved upon mergesort in factso farwe really haven' in order to do betterwe must avoid using significant extra memory and have inner loops that are clean thus quicksort is commonly written in manner that avoids creating the second group (the equal items)and the algorithm has numerous subtle details that affect the performancetherein lies the complications we now describe the most common implementation of quicksort--"classic quicksort,in which the input is an arrayand in which no extra arrays are created by the algorithm the classic quicksort algorithm to sort an array consists of the following four easy steps if the number of elements in is or then return pick any element in this is called the pivot partition { (the remaining elements in sinto two disjoint groupss { { }| return {quicksort( followed by followed by quicksort( )since the partition step ambiguously describes what to do with elements equal to the pivotthis becomes design decision part of good implementation is handling this case as efficiently as possible intuitivelywe would hope that about half the elements that are equal to the pivot go into and the other half into much as we like binary search trees to be balanced figure shows the action of quicksort on set of numbers the pivot is chosen (by chanceto be the remaining elements in the set are partitioned into two smaller sets recursively sorting the set of smaller numbers yields (by rule of recursionthe set of large numbers is similarly sorted the sorted arrangement of the entire set is then trivially obtained it should be clear that this algorithm worksbut it is not clear why it is any faster than mergesort like mergesortit recursively solves two subproblems and requires linear additional work (step )butunlike mergesortthe subproblems are not guaranteed to be of equal sizewhich is potentially bad the reason that quicksort is faster is that the partitioning step can actually be performed in place and very efficiently this efficiency more than makes up for the lack of equal-sized recursive calls the algorithm as described so far lacks quite few detailswhich we now fill in there are many ways to implement steps and the method presented here is the result of extensive analysis and empirical study and represents very efficient way to implement quicksort even the slightest deviations from this method can cause surprisingly bad results picking the pivot although the algorithm as described works no matter which element is chosen as pivotsome choices are obviously better than others