Подсчитаем время выполнения параллельного алгоритма сортировки «пузырьком». В течение каждой итерации алгоритма производится O(n) сравнений, для того, чтобы объединить два блока. Трудоемкость коммуникации процессоров - O(n). Сумма времен внутренних сортировок каждым процессором равна O(n/p*log(n/p)). Следовательно, можем получить теоретическую оценку времени выполнения параллельного алгоритма:

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

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

где t - время выполнения базовой операции сортировки.

Ускорение S и эффективность E мы можем найти следующим образом:

Если количество процессоров совпадает с числом сортируемых данных (т.е. p=n), эффективность использования процессоров падает с ростом n. Получение асимптотически ненулевого значения показателя E может быть обеспечено при количестве процессоров, пропорциональ­ных величине log(n).