Параллельная сортировка осуществляется следующим образом. Сначала массив делится на p равных частей, где p – число вычислительных узлов. Каждый узел сортирует свою чатсь из n/p элементов с помощью последовательного алгоритма пузырьковой сортировки. Далее происходит чередование чет-нечетных «перестановок» на p итерациях. На нечетных итерациях пары узлов с номерами (0,1)(2,3)(4,5)… обмениваются друг с другом своими частями сортируемой последовательности. При этом каждый узел сливает свою часть с полученной от соседа. Из этих 2*n/p элементов узел с меньшим номером оставляет себе первую половину, а узел с большим номером – большую. На четной итерации происходит аналогичный обмен между узлами с номерами (1,2)(3,4)(5,6)(7,8)…. После проведения p итераций на первом узле лежит првая группа из n/p элементов отсортированной последовтельности, на втором узле – вторая и так далее.