Найдите медиану параллельно

Использовать алгоритм выбора.

1. Разделить массив чисел на 100 разделов.
2. Каждый процессор должен использовать общую опору для разделения массива на две группы (левая / правая)
3. , затем каждый процессор должен отправить размер этих 2 групп лидеру
4. лидер должен вычислить, какая группа меньше и передайте сообщение, чтобы избавиться от одной из этих групп.
5. вернитесь к шагу 2, пока не найдете медианное значение

. Среднее время выполнения этого решения составляет O (n). чтобы сделать его асимптотическим время выполнения O (n), каждый процессор должен разделить числа на группы из 5 элементов, найти медиану каждой группы (используя сортировку вставкой) и отправив эти медианы обратно лидеру, лидер выберет медианное значение этих медиан (используя тот же алгоритм), и это будет стержнем

прочтите статью в вики - http://en.wikipedia.org/wiki/Selection_algorithm