contains only points in the stripand these points are guaranteed to be sorted by their coordinates this strategy ensures that the entire algorithm is ( log )because only (nextra work is performed the selection problem the selection problem requires us to find the kth smallest element in collection of elements of particular interest is the special case of finding the median this occurs when  / in and we have seen several solutions to the selection problem the solution in uses variation of quicksort and runs in (naverage time indeedit is described in hoare' original paper on quicksort although this algorithm runs in linear average timeit has worst case of ( selection can easily be solved in ( log nworst-case time by sorting the elementsbut for long time it was unknown whether or not selection could be accomplished in (nworst-case time the quickselect algorithm outlined in section is quite efficient in practiceso this was mostly question of theoretical interest recall that the basic algorithm is simple recursive strategy assuming that is larger than the cutoff point where elements are simply sortedan element vknown as the pivotis chosen the remaining elements are placed into two setss and contains elements that are guaranteed to be no larger than vand contains elements that are no smaller than finallyif <| |then the kth smallest element in can be found by recursively computing the kth smallest element in if | then the pivot is the kth smallest element otherwisethe kth smallest element in is the ( | )st smallest element in the main difference between this algorithm and quicksort is that there is only one subproblem to solve instead of two in order to obtain linear algorithmwe must ensure that the subproblem is only fraction of the original and not merely only few elements smaller than the original of coursewe can always find such an element if we are willing to spend some time to do so the difficult problem is that we cannot spend too much time finding the pivot for quicksortwe saw that good choice for pivot was to pick three elements and use their median this gives some expectation that the pivot is not too bad but does not provide guarantee we could choose elements at randomsort them in constant timeuse the th largest as pivotand get pivot that is even more likely to be good howeverif these elements were the largestthen the pivot would still be poor extending thiswe could use up to ( /log nelementssort them using heapsort in (ntotal timeand be almost certainfrom statistical point of viewof obtaining good pivot in the worst casehoweverthis does not work because we might select the ( /log nlargest elementsand then the pivot would be the [ ( /log )]th largest elementwhich is not constant fraction of the basic idea is still useful indeedwe will see that we can use it to improve the expected number of comparisons that quickselect makes to get good worst casehoweverthe key idea is to use one more level of indirection instead of finding the median from sample of random elementswe will find the median from sample of medians