Find a median in parallel

Question

If you have one huge amount of numbers and one hundred computers, How would you find the median of the numbers?

Answer 1

Use selection algorithm.

1. Split the array of number to 100 partitions.
2. Each processor should use the general pivot to split the array to two groups (left/right)
3. then each processor should send the size of those 2 groups to the leader
4. the leader should calculate which group is smaller and broadcast a message to get rid from one of those groups.
5. go back to step 2 until you find the median

this solution has an avg runtime of O(n) in order to make it asymptotic runtime of O(n), each processor should split the numbers to groups of 5 elements find the median of each group (using insertion sort) and send those medians back to the leader, the leader will choose the median of those medians (using the same algo) and that will be the pivot

read the wiki article - http://en.wikipedia.org/wiki/Selection_algorithm