Трудоёмкость последовательного алгоритма в среднем составляет n*log(n) оперций.

Оценим трудоёмкость параллельного алгоритма. Сортировка локальных последовательностей - n/p log(n/p). Во время слияния мы производим log(p) параллельных шагов слияния. Получаем последовательность 2n/p, 4n/p, 8n/p,..., n/p * 2^log(p). Сумма этой последовательности равна 2n * (p - 1) / p или, если несколько огрубить, 2n.

Итого получаем сложность

n/p log(n/p) + 2n

Эффективность алгоритма в данном случае

p*log(n) / (log(n/p) + 2p) Ускорение log(n) / (log(n/p) + 2p)

Общее время всех выполняемых в ходе сортировки операций передачи блоков можно оценить при помощи соотношения вида

T_p(comm)=p(a+w(n/p)/b), где a - латентность, b - пропускная способность сети передачи данных, w - размер элемента упорядочиваемых данных в байтах.
С учетом трудоемкости коммуникационных действий общее время выполнения параллельного алгоритма сортировки определяется следующим выражением (t-время выполнения базовой операции сортировки): T_p=((n/p)log₂(n/p)+2n)t+p(a+w(n/p)/b)