items being sorted that ishalf the items should be larger than the pivotand half smaller this would result in the array being partitioned into two subarrays of equal size two equal subarrays is the optimum situation for the quicksort algorithm if it has to sort one large and one small arrayit' less efficient because the larger subarray has to be subdivided more times the worst situation results when subarray with elements is divided into one subarray with element and the other with - elements (this division into cell and - cells can also be seen in steps and in figure if this and - division happens with every partitionthen every element requires separate partition step this is in fact what takes place with inversely sorted datain all the subarraysthe pivot is the smallest itemso every partition results in an - element in one subarray and only the pivot in the other to see this unfortunate process in actionstep through the quicksort workshop applet with inversely sorted bars notice how many more steps are necessary than with random data in this situation the advantage gained by the partitioning process is lost and the performance of the algorithm degenerates to ( besides being slowthere' another potential problem when quicksort operates in ( time when the number of partitions increasesthe number of recursive function calls also increases every function call takes up room on the machine stack if there are too many callsthe machine stack may overflow and paralyze the system to summarizein the quicksort appletwe select the rightmost element as the pivot if the data is truly randomthis isn' too bad choicebecause usually the pivot won' be too close to either end of the array howeverwhen the data is sorted or inversely sortedchoosing the pivot from one end or the other is bad idea can we improve on our approach to selecting the pivotmedian of three partitioning many schemes have been devised for picking better pivot the method should be simple but have good chance of avoiding the largest or smallest value picking an element at random is simple but--as we've seen--doesn' always result in good selection howeverwe could examine all the elements and actually calculate which one was the median this would be the ideal pivot choicebut the process isn' practicalas it would take more time than the sort itself compromise solution is to find the median of the firstlastand middle elements of the arrayand use this for the pivot (the median or middle item is the data item chosen so that exactly half the other items are smaller and half are larger picking the median of the firstlastand middle elements is called the median-of-three approach and is shown in figure figure the median of three