Изменения

* '''Шаг 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.''' Данные из процессоров поочерёдно записываем в исходный массив. Данные отсортированы.

После обмена данными будет произведено слияние <tex>p</tex> массивов в каждом процессоре. Также мы должны помнить, что при равномерном распределении данных длина сливаемых массивов будет <tex dpi=145>\frac {n}{p^2}</tex>, а <tex>\mathrm {merge} </tex> двух массивов выполняется за сумму их длин. Поэтому <tex>\mathrm {merge} </tex> займёт <tex dpi=145> O(\sum \limits_{k=2}^{p} \frac {k \cdot n}{p^2})=O(\frac {n \cdot p \cdot (p+1)}{2p^2}-\frac {n}{p^2})=O(n)</tex>. <br>

<tex dpi=145> O(\frac {n\log(n/p)}{p})+O(p^2\log(p))+O(n)+O(p)</tex> <br> Что равно: <br> 

== Источники информации ==* [[wikipedia:ruhttps:Сортировка слиянием//wiki.engr.illinois.edu/download/attachments/99155993/Sort+ParaProg(Quinn)chpt14.5.pdf?version=1&modificationDate=1203641170000|Сортировка слиянием {{---}} Википедия]Статья о PSRS]* [[wikipedia:ruhttp:Быстрая сортировка//users.cms.caltech.edu/~cs284/lectures/29oct97/sld003.htm|Быстрая сортировка {{---}} Википедия]Презентация]