Рассмотрим N-мерный гиперкуб из p=2^N процессоров (p < N).

Cложность алгоритма сортировки.

После разделения исходного набора данных, каждый процессор выполняет разбиение своего блока на два, согласно ведущему элементу. Это может быть выполнено за n/p операций (будем предполагать, что на каждой итерации сортировки каждый блок делится на равные по размеру части). Также, на каждой из итераций, каждый процессор выполняет слияние частей блоков, сложность этой операции оценивается величиной (n/p). После всех итераций, мы выполняем последовательную операцию быстрой сортировки. Таким образом, общее время вычислений параллельного алгоритма быстрой сортировки оценивается величиной [2(n/p)(log₂p) + (n/p)log₂ (n/p)]*t, где t есть время выполнения базовой операции перестановки.

Сложность выполняемых коммуникационных операций.

Общее количество межпроцессорных обменов для рассылки ведущего элемента на N-мерном гиперкубе может быть ограничено оценкой (log₂p)^2. При используемых предположениях (выбор ведущих элементов осуществляется самым наилучшим образом, количество итераций алгоритма равно (log₂p), а объем передаваемых данных между процессорами всегда является равным половине блока, т.е. (n/p)/2), коммуникационная сложность параллельного алгоритма быстрой сортировки определяется при помощи соотношения (α+w/β)(log₂p)^2 + (α+w(n/2p)/β)(log₂p), где α - латентность, β - пропускная способность сети, а w – размер элемента набора в байтах.

Общая трудоемкость алгоритма

С учетом полученных соотношений, она =[2(n/p)(log₂p) + (n/p)log₂(n/p)]*t + (α+w/β)(log₂p)^2 + (α+w(n/2p)/β)(log₂p).