what are the consequences of the worst case behavior mentioned above to the performance quicksortwe have realized that each split results in right partition of only single elementthe request to sort this partition is stacked for later execution consequentlythe maximum number of requestsand therefore the total required stack sizeis this isof coursetotally unacceptable (note that we fare no better -in fact even worse -with the recursive version because system allowing recursive activation of procedures will have to store the values of local variables and parameters of all procedure activations automaticallyand it will use an implicit stack for this purpose the remedy lies in stacking the sort request for the longer partition and in continuing directly with the further partitioning of the smaller section in this casethe size of the stack can be limited to log(nthe change necessary is localized in the section setting up new requests it now reads if then if then (*stack request for sorting right partition*inc( )low[ :ihigh[ : endr : (*continue sorting left partition*else if then (*stack request for sorting left parition*inc( )low[ :lhigh[ : endl : (*continue sorting right partition*end finding the median the median of items is defined as that item which is less than (or equal tohalf of the items and which is larger than (or equal tothe other half of the items for examplethe median of is the problem of finding the median is customarily connected with that of sortingbecause the obvious method of determining the median is to sort the items and then to pick the item in the middle but partitioning yields potentially much faster way of finding the median the method to be displayed easily generalizes to the problem of finding the -th smallest of items finding the median represents the special case / the algorithm invented by hoare [ - functions as follows firstthe partitioning operation of quicksort is applied with and - and with ak selected as splitting value the resulting index values and are such that ah for all ah for all > there are three possible cases that may arise the splitting value was too smallas resultthe limit between the two partitions is below the desired value the partitioning process has to be repeated upon the elements ai ar (see fig < >