the same bad properties as merely choosing the first element do not use that pivoting strategyeither safe maneuver safe course is merely to choose the pivot randomly this strategy is generally perfectly safeunless the random number generator has flaw (which is not as uncommon as you might think)since it is very unlikely that random pivot would consistently provide poor partition on the other handrandom number generation is generally an expensive commodity and does not reduce the average running time of the rest of the algorithm at all median-of-three partitioning the median of group of numbers is the  / th largest number the best choice of pivot would be the median of the array unfortunatelythis is hard to calculate and would slow down quicksort considerably good estimate can be obtained by picking three elements randomly and using the median of these three as pivot the randomness turns out not to help muchso the common course is to use as pivot the median of the leftrightand center elements for instancewith input as beforethe left element is the right element is and the center (in position (left right)/ element is thusthe pivot would be using median-of-three partitioning clearly eliminates the bad case for sorted input (the partitions become equal in this caseand actually reduces the number of comparisons by partitioning strategy there are several partitioning strategies used in practicebut the one described here is known to give good results it is very easyas we shall seeto do this wrong or inefficientlybut it is safe to use known method the first step is to get the pivot element out of the way by swapping it with the last element starts at the first element and starts at the next-to-last element if the original input was the same as beforethe following figure shows the current situation for nowwe will assume that all the elements are distinct later onwe will worry about what to do in the presence of duplicates as limiting caseour algorithm must do the proper thing if all of the elements are identical it is surprising how easy it is to do the wrong thing what our partitioning stage wants to do is to move all the small elements to the left part of the array and all the large elements to the right part "smalland "largeareof courserelative to the pivot while is to the left of jwe move rightskipping over elements that are smaller than the pivot we move leftskipping over elements that are larger than the pivot when and have stoppedi is pointing at large element and is pointing at small element if