Определим эффективность последовательной и параллельной версии.

Трудоемкость последовательной версии пузырьковой сортировки O(n^2).

Параллельный алгоритм состоит из 2-х этапов. На первом каждый узел сортирует свою часть данных. Трудоемкость этой операции O((n/p)^2). На втором этапе происходят обмены между процессорами. При этом части сортируемых данных сливаются в единый массив за время O(2*n/p). Таких итераций не более p. В итоге имеем оценку времени параллельной версии O((n/p)^2 + 2*n)

Ускорение и эффективность:

S=(n*p^2)/(n+2*p^2)

E=(n*p)/(n+2*p^2)