algorithm design techniques the basic pivot selection algorithm is as follows arrange the elements into / groups of five elementsignoring the (at most fourextra elements find the median of each group this gives list of / medians find the median of return this as the pivotv we will use the term median-of-median-of-five partitioning to describe the quickselect algorithm that uses the pivot selection rule given above we will now show that median-of-median-of-five partitioning guarantees that each recursive subproblem is at most roughly percent as large as the original we will also show that the pivot can be computed quickly enough to guarantee an (nrunning time for the entire selection algorithm let us assume for the moment that is divisible by so there are no extra elements suppose also that / is oddso that the set contains an odd number of elements this provides some symmetryas we shall see we are thus assumingfor conveniencethat is of the form we will also assume that all the elements are distinct the actual algorithm must make sure to handle the case where this is not true figure shows how the pivot might be chosen when in figure represents the element which is selected by the algorithm as pivot since is the median of nine elementsand we are assuming that all elements are distinctthere must be four medians that are larger than and four that are smaller we denote these by and srespectively consider group of five elements with large median (type lthe median of the group is smaller than two elements in the group and larger than two sorted groups of five elements medians figure how the pivot is chosen