What's the fastest algorithm to find the median for numbers on different machines?

If I have m machines, and an equal number n of numbers on each machine, what is the fastest algorithm to find the开发者_开发知识库 median of ALL of these numbers, i.e., all of the m*n numbers? There are two cases I'd like to look at: each n numbers sorted or unsorted.

Does anyone have some references, or some ideas to share? Thank you!

Median of medians can be adapted over multiple machines, especially if they all have the same number of elements.

Michael's solution is an adaptation of quickselect. They both work, but quickselect is usually faster, despite being O(nlogn) compared to median of median's O(n).