77
правок
Изменения
→Алгоритм
== Алгоритм ==
* Начало.
* '''Шаг 1''' Исходный массив в <tex>n</tex> элементов разделим поровну между <tex>p</tex> процессорами.
* '''Шаг 2''' На каждом процессоре запускам [[Быстрая сортировка|быструю сортировку]].
* '''Шаг 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''' Данные из процессоров поочерёдно записываем в исходный массив. Данные отсортированы.
* Конец.
== Пример ==
