9.7 Order Statistics

• Given a list of n records, and an integer k, find the record whose key is the k^th in the sorted order of keys.
• Note that
  

  K = 1  corresponds to finding the minimum (9.7)

  K = n  corresponds to finding the maximum (9.8)

  $${\frac{n}{2}}$$ K =