Параллельные сортировки на общей памяти

Сортировка на линейных сетях
Если число процессоров равно числу сортируемых значений , то сортировку можно осуществить, передавая сети в каждом цикле одно значение. Первый процессор читает поданное значение, сравнивает его с текущим и передает его большее значение своему соседу. Остальные процессоры делают то же самое : сохраняют меньшее из двух значений и пересылают большее следующему звену в цепочку.

Сортировка на линейных сетях
A.

Сортировка на линейных сетях
B.

Сортировка на линейных сетях
В.

Характеристики :
В общем случае алгоритм выполняет 2 * (N — 1) + 1 (т.е. O(N)), действий.
В работе принимают участие N процессоров => стоимость алгоритма равна O(N ), что эквивалентно самым медленным нашим сортировкам.
Сортировка на линейных сетях

Четно-нечетная сортировка перестановками
В четно нечетной сортировке сравниваются соседние значения и при необходимости переставляются.

Четно-нечетная сортировка перестановками
Пример для списка : 15, 18, 13, 12, 17, 11, 19, 16, 14

Четно-нечетная сортировка перестановками
Все сравнения происходят параллельно, поэтому всякий проход цикла выполняет два сравнения и общее время работы равно O(N).
Стоимость алгоритма равна величине N/2 * O(N) — несколько меньше, чем у предыдущего алгоритма, но все равно порядка O(N^2).
Характеристики

Другие алгоритмы
Если у нас список без повторений, то мы можем отсортировать его с помощью подсчета. С одним процессором на каждое входное значение местоположение каждого элемента можно определить за O(N) сравнений. Нам требуется N процессоров, поэтому стоимость такого подхода равна O(N^2).
Еще существуют способы параллельного слияния двух списков, реализующие оптимальную стоимость O(N). При использовании не более чем N/ log(N) процессоров. Разбив список на N/ log(N) частей, и отсортировав каждую из них эффективным