Finding the Median 1 Median Finding - Massachusetts Institute of Technology

Finding the Median Prof. Michel Goemans 1 Median Finding Suppose we have a list of n keys that are completely unsorted. If we want to find the largest or the smallest key, it is very easy to do so with n−1 comparisons. If we want to find the mth largest key then you can use heapsort to do it in cn+cmlog(n) comparisons for some c. ................
................