Randomized Median Finding and Quicksort

1 Randomized Median Finding Consider the problem of nding the median of a list of n elements, or more generally the element of rank m. One natural approach is to select a pivot element p, to compute its rank, and partition the list into 2 sublists, one containing the elements smaller than p, the other containing those ................
................