Each computer finds the median of the numbers it holds. This can be
done in O(n) time and O(n) space by each computer. Now all computers
send their median to a dedicated computer which finds the median of
these medians ( O(n) time and space) and sends this value to all the
computers. Each computer in turn partitions the numbers it has (O(n)
time and space) according to this median of medians and sends how many
numbers are less and greater than the median of medians to the
dedicated computer. This leaves us with around n^2/4 numbers less than
the median of median and n^2/4 numbers greater than the median of
medians. So now we need to repeat the process with around n^2/2
elements.
