Question. A median of a list of n numbers is defined to be a value x in the list such that at least n/2 values in the list are ≤ x, and at least n/2 values in the list are ≥ x. (Note that at least one value in the list is ≤ x, since x is in the list.) Describe an algorithm that finds a median of a list in time O(nlg(n)).
Answer. Use Mergesort to sort the list. That takes time O(nlg(n)). Now select the middle value in the list. (If the list has n values, the middle value is the one at index ceiling(n/2), numbering starting at 1.)