In the above problem,
choose the pivot as follows. Divide the elements into
groups of 7, leaving aside between 0 and 6 elements that
cannot be placed in a group. Sort each group and take the middle
element from each group. Choose the median of these middle elements
as the pivot.
Let T(n) be the time taken by a call to select on
n elements. Write down an appropriate recurrence for T(n) and
show that it is O(n).