PSRS-сортировка

Описание

Parallel Sorting by Regular Sampling — параллельная сортировка, разработанная Ханмао Ши, Рисажем Канселом и Джонатаном Шеффером в 1992 году. Имеет два преимущества по сравнению с быстрой сортировкой:

• сохраняет размер списка более сбалансированным на протяжении всего процесса
• избегает повторных перестановок ключей

Алгоритм

На вход подаётся [math]n[/math] элементов. Для начала надо разделить входные данные на [math]p[/math] равных частей, где [math]p[/math] — количество процессоров. Далее запустить алгоритм быстрой сортировки на каждом из процессоров. Далее мы должны сформировать массив элементами которого будут элементы из каждого процессора с индексами [math]0,\frac {n} {p^2}, \frac {2n}{p^2},...,\frac {(p-1)n}{p^2}[/math]. Теперь нам потребуется отсортировать полученный массив и выбрать из него p разделителей с индексами [math] p + [\frac {p} {2}] - 1, 2p + [\frac {p}{2}] - 1,...,(p-1)p + [\frac {p}{2}] - 1[/math]. После чего разделим данные в процессорах согласно полученному массиву разделителей. Пусть [math]a_1, a_2,..., a_j[/math] — разделители. Разделение происходит следующим образом, данные в каждом процессоре разобьём на группы элементов, попадающие в соответствующие полуинтервалы [math](-\infty,a_1],(a_1,a_2],...,(a_j,+\infty)[/math]. Далее сольём соответствующие группы, которые отсортированы по возрастанию, в массивы. Слияние будем производить поочерёдно, то есть сначала сольём первую группу со второй потом результат с третей и так далее. В итоге получим отсортированный набор данных.

Пример

Количество элементов [math]27[/math], количество процессоров [math]3[/math]. Исходный набор данных:

[math][15, 46, 48, 93, 39, 6, 72, 91, 14, 36, 69, 40, 89, 61, 97, 12, 21, 54, 53, 97, 84, 58, 32, 27, 33, 72, 20][/math]:

Описание этапа	1 процессор	2 процессор	3 процессор
Разделение между процессорами	15 46 48 93 39 6 72 91 14	36 69 40 89 61 97 12 21 54	53 97 84 58 32 27 33 72 20
После сортировки частей	6 14 15 39 46 48 72 91 93	12 21 36 40 54 61 69 89 97	20 27 32 33 53 58 72 84 97
Выбор элементов	6 14 15 39 46 48 72 91 93	12 21 36 40 54 61 69 89 97	20 27 32 33 53 58 72 84 97

Описание этапа	Данные
Выбранные элементы	6 39 72 12 40 69 20 33 72
После сортировки	6 12 20 33 39 40 69 72 72
Выбор элементов	6 12 20 33 39 40 69 72 72
Разделители	33 69

Описание этапа		1 процессор			2 процессор			3 процессор
После сортировки частей	6 14 15	39 46 48	72 91 93	12 21	36 40 54 61 69	89 97	20 27 32 33	53 58	72 84 97
После обмена данными	6 14 15	12 21	20 27 32 33	39 46 48	36 40 54 61 69	53 58	72 91 93	89 97	72 84 97
После слияния	6 12 14	15 20 21	27 32 33	36 39 40	46 48 53	54 58 61 69	72 72	84 89 91	93 97 97

Анализ

При [math]n[/math] элементах и [math]p[/math] процессорах начальная сортировка выполнится за [math]O( \frac {n\log(n/p)}{p})[/math]. Выбор порядка [math]p[/math] элементов в каждом процессоре произойдёт за [math]O(p)[/math], их сортировать мы будем с помощью быстрой сортировки, а так же учитывая, что их количество порядка [math]p[/math], то можно сказать, что они сортируются за [math]O(p^2\log(p^2))=O(p^2\log(p))[/math]. После обмена данными будет произведено слияние [math]p[/math] массивов в каждом процессоре, учитывая что при равномерном распределении данных длина сливаемых массивов будет [math]\frac {n}{p^2}[/math], а [math]\mathrm {merge} [/math] двух массивов выполняется за сумму их длин, это займёт [math] 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)[/math]. В итоге мы получим [math] O(\frac {n\log(n/p)}{p})+O(p^2\log(p))+O(n)+O(p)[/math][math] =O(\frac {n\log(n/p)}{p}+p^2\log(p)+\frac {n}{p\log p}+p)=O(\frac {n\log(n/p)}{p})[/math].

См. также

• Многопоточная сортировка слиянием