Последовательный метод сортировки пузырьком характеризуется квадратичной оценкой . Однако применение подобной оценки сложности последовательного алгоритма приведет к искажению исходного целевого назначения критериев качества параллельных вычислений – показатели эффективности в этом случае будут характеризовать используемый способ параллельного выполнения данного конкретного метода сортировки, а не результативность использования параллелизма для задачи упорядочивания данных в целом как таковой. Различие состоит в том, что для сортировки могут быть применены более эффективные последовательные алгоритмы, трудоемкость которых имеет порядок , и для сравнения, насколько быстрее могут быть упорядочены данные при использовании параллельных вычислений, в обязательном порядке должна использоваться именно данная оценка сложности.

на начальной стадии работы метода каждый процессор проводит упорядочивание своих блоков данных (размер блоков при равномерном распределении данных является равным n/p). Предположим, что данная начальная сортировка может быть выполнена при помощи быстродействующих алгоритмов упорядочивания данных, тогда трудоемкость начальной стадии вычислений можно определить выражением вида: .

Далее на каждой выполняемой итерации параллельной сортировки взаимодействующие пары процессоров осуществляют передачу блоков между собой, после чего получаемые на каждом процессоре пары блоков объединяются при помощи процедуры слияния. Общее количество итераций не превышает величины p, и, как результат, общее количество операций этой части параллельных вычислений оказывается равным .

С учетом полученных соотношений показатели эффективности и ускорения параллельного метода сортировки имеют вид:

Учтем длительность выполняемых вычислительных операций и оценим трудоемкость операции передачи блоков между процессорами: ,

где a - латентность, b - пропускная способность сети передачи данных, w - размер элемента упорядочиваемых данных в байтах. Таким образом общее время выполнения параллельного алгоритма: , где тау - время выполнения базовой операции сортировки.