advanced sorting int partition partitionit(leftrightpivot)recquicksort(leftpartition- )/sort left side recquicksort(partition+ right)/sort right side if partitionit(is called with left and right for exampleand happens to return as the partitionthen the range supplied in the first call to recquicksort(will be ( - and the range to the second will be ( - this is normal the base case in recquicksort(is activated by array sizes less than as well as by so it will return immediately for negative ranges negative ranges are not shown in figure although they do cause (briefcalls to recquicksort(degenerates to ( performance if you use the quicksort workshop applet to sort inversely sorted barsyou'll see that the algorithm runs much more slowly and that many more dotted horizontal lines are generatedindicating more and larger subarrays are being partitioned what' happening herethe problem is in the selection of the pivot ideallythe pivot should be the median of the 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 having 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 - elements 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 choice because usually the