Обсуждение:PSRS-сортировка

Распараллеливание простых сортировок

Параллельная сортировка пузырьком

Сначала главный процессор разбивает исходный массив длиной [math]z[/math] элементов на [math]p[/math] равных частей блоков. Каждый блок содержит [math]p=z/n[/math] элементов массива. Полученные блоки рассылаются по процессам. Далее идет предобработка. На этапе предобработки каждый процесс сортирует свой массив методом пузырьковой сортировки. Далее происходит чередование чет-нечетных перестановок на p итерациях. На нечетной итерации пары процессов с номерами [math](0,1)(2,3)(4,5)…[/math] обмениваются друг с другом массивами, при этом выполняется слияние блоков, после чего на процессе с меньшим номером остается [math]n/p[/math] первых упорядоченных элементов объединенного массива, а на процессе с большим номером остается [math]n/p[/math] последних упорядоченных элементов объединенного массива. На четной итерации происходит все точно так же, но обмен производится между процессами с номерами [math](1,2)(3,4)(5,6)(7,8)…[/math] . Если в течении двух последовательных четной и нечетной итерации не производится никаких изменений, то алгоритм может прекратить свою работу заранее. После этого части массивов отсылаются на главный процесс и там объединяются, после чего получается отсортированный массив. Предобработка занимет [math]p^2[/math] тактов после чего происходит максимум [math]n[/math] слияний. Осознать, что максимально количество слияний можно, представив частный случай. Пусть минимальный элемент оказался в последнем блоке тогда за за каждое слияние он будет перемещаться на один блок влево. После [math]n[/math] слияний он окажется в первом блоке. В итоге время сортировки сократится с [math] z^2 [/math] до [math] p^2+2pn\log (2*p)[/math] .