Изменения

* '''Шаг 1.''' Исходный массив в <tex>n</tex> элементов разделим поровну между <tex>p</tex> процессорами.* '''Шаг 2.''' На каждом процессоре запускам [[Быстрая сортировка|быструю сортировку]].* '''Шаг 3.''' Формируем вспомогательный массив из элементов каждого процессора под индексами <tex dpi=145>0,\frac {n} {p^2}, \frac {2n}{p^2},...,\frac {(p-1)n}{p^2}</tex>.* '''Шаг 4.''' Сортируем вспомогательный массив с помощью быстрой сортировки.* '''Шаг 5.''' Формируем массив разделителей из элементов вспомогательного массива под индексами <tex dpi=145> p + [\frac {p} {2}] - 1, 2p + [\frac {p}{2}] - 1,...,(p-1)p + [\frac {p}{2}] - 1</tex>.* '''Шаг 6.''' Делим данные в процессорах с помощью массива разделителей следующим образом. Пусть <tex>a_1, a_2,..., a_j</tex> {{---}} разделители. Тогда данные в каждом процессоре разобьём на группы элементов, попадающие в соответствующие полуинтервалы <tex>(-\infty,a_1],(a_1,a_2],...,(a_j,+\infty)</tex>.* '''Шаг 7.''' Сливаем соответствующие группы элементов в массивы. Слияние будем производить поочерёдно, то есть сначала сольём первую группу со второй потом результат с третей и так далее. В итоге получим отсортированный набор данных.* '''Шаг 8.''' Данные из процессоров поочерёдно записываем в исходный массив. Данные отсортированы.