to start withor the large element originally in position was replaced during swap similar argument shows that elements in positions must be large one important detail we must consider is how to handle elements that are equal to the pivot the questions are whether or not should stop when it sees an element equal to the pivot and whether or not should stop when it sees an element equal to the pivot intuitivelyi and ought to do the same thingsince otherwise the partitioning step is biased for instanceif stops and does notthen all elements that are equal to the pivot will wind up in to get an idea of what might be goodwe consider the case where all the elements in the array are identical if both and stopthere will be many swaps between identical elements although this seems uselessthe positive effect is that and will cross in the middleso when the pivot is replacedthe partition creates two nearly equal subarrays the mergesort analysis tells us that the total running time would then be ( log nif neither nor stopsand code is present to prevent them from running off the end of the arrayno swaps will be performed although this seems gooda correct implementation would then swap the pivot into the last spot that touchedwhich would be the next-tolast position (or lastdepending on the exact implementationthis would create very uneven subarrays if all the elements are identicalthe running time is ( the effect is the same as using the first element as pivot for presorted input it takes quadratic time to do nothingthuswe find that it is better to do the unnecessary swaps and create even subarrays than to risk wildly uneven subarrays thereforewe will have both and stop if they encounter an element equal to the pivot this turns out to be the only one of the four possibilities that does not take quadratic time for this input at first glance it may seem that worrying about an array of identical elements is silly after allwhy would anyone want to sort , identical elementshoweverrecall that quicksort is recursive suppose there are , , elementsof which , are identical (ormore likelycomplex elements whose sort keys are identicaleventuallyquicksort will make the recursive call on only these , elements then it really will be important to make sure that , identical elements can be sorted efficiently small arrays for very small arrays ( < )quicksort does not perform as well as insertion sort furthermorebecause quicksort is recursivethese cases will occur frequently common solution is not to use quicksort recursively for small arraysbut instead use sorting algorithm that is efficient for small arrayssuch as insertion sort using this strategy can actually save about percent in the running time (over doing no cutoff at alla good cutoff range is although any cutoff between and is likely to produce similar results this also saves nasty degenerate casessuch as taking the median of three elements when there are only one or two actual quicksort routines the driver for quicksort is shown in figure