Здравствуйте, scf, Вы писали:

scf>Все ключи пересекаются, ключей сотни миллионов (иначе зачем алгоритмы городить), по каждому ключу несколько тысяч значений, поэтому средние могут быть любыми.

Тогда тестировать надо. Скачать себе все ноды, и прогнать тест на них, сколько пересылок получится до остановки. И распределения неплохо бы построить, типа, как выглядят средние на каждой ноде после сортировки, в зависимости от порядкового номера в отсортированном массиве. Чем больше наклон, тем меньше пересылок нужно.