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

void SimpleSort(int* mas, int n)

{

for(int i=0; i

{

       if(i%2==0)

       {

             for(int j=0;j

             {

                   CompareExchange(mas,2*j,2*j+1);

             }

             if(n%2==0)

             {

                   CompareExchange(mas,n-2,n-1);

             }

       }

       if(i%2==1)

     {

             for(int j=1; j

             {

                   CompareExchange(mas,2*j-1,2*j);

             }

       }

}

}

Сравнения пар значений на итерациях являются независимыми и могут быть распараллелены.   В случае, когда кол-во процессоров меньше кол-ва элементов, на каждый процессор отводятся блоки размером n/p.