Пусть у нас имеется N-мерный гиперкуб, состоящий из p=2^N процессоров, где p < N.

Определим вначале вычислительную сложность алгоритма сортировки.
После разделения исходного набора данных, каждый процессор выполняет сортировку своего блока, что может быть выполнено при использовании последовательного алгоритма быстрой сортировки за (n/p)log₂(n/p) операций.
На каждой из (log₂p) итераций сортировки каждый процессор осуществляет деление блока относительно ведущего элемента, сложность этой операции составляет (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).