Изменения

<b>Перестановочная сортирующая сеть (permutation sorting network)</b> {{---}} сеть сортировки, содержащая последовательность компараторов <tex>[i_1:j_1]...[i_r:j_r]</tex>, где каждый модуль <tex>[i:j] </tex> может устанавливаться извне в одно из двух остояний: либо он передает свои входы без изменений, либо меняет местами <tex>x_i</tex> и <tex>x_j</tex> <tex> (</tex>независимо от значений <tex>x_i</tex> и <tex>x_j)</tex>).

| [[Файл:permutation_network.png|thumb|300px|На рисунке показана рекурсивная схема перестановочной сети <tex>P_8</tex> на <tex>8</tex> входов и <tex>8</tex>, которая содержит две копии <tex>P_4</tex> и <tex>8</tex> переключателей (<tex>(P_2)</tex>).]] || [[Файл:permutation_sorting_network.png|thumb|300px|Перестановочная сортирующая сеть для <tex>n=5</tex>]]

<b>Периодическая сортировочная сеть (periodic sorting network)</b> на <tex>n</tex> входов <tex><a_1,a_2,...,a_n></tex> {{---}} сеть сортировки, содержащая <tex>n = 2^t</tex> входов</tex>, где <tex>t</tex> {{--- }} уровень сети, и у которой каждый уровень может быть построен с помощью рекурсивного алгоритма.

Если входные числа <tex>2^k</tex> - упорядочены при некотором <tex>k \geqslant 1</tex>, то периодическая сеть приведет к выходу, который будет <tex>2^{k-1}</tex> - упорядочен.

Теперь можно увидеть, что первые <tex>t-1</tex> уровней сети состоят из двух отдельных сетей: одна из <tex>2^{t-1}</tex> красных линий, а другая {{- --}} из <tex>2^{t-1}</tex> синих линий. Компараторы на <tex>t</tex>-м уровне образуют сеть слияния, как в сетях битонного или четно-нечетного слияния. Таким образом, мы получили искомый результат при <tex>k=1</tex>.

Такой способ так же годится и для случая <tex>k=2</tex>. Если вход <tex>4</tex>-упорядочен, красные линии содержат <tex>2^{t-1}</tex> чисел, которые являются <tex>2</tex>-упорядоченными; то же самое можно сказать относительно синих линий.Очевидно, что результат является <tex>2</tex>-упорядоченным.

Теперь для <tex>k \geqslant 2</tex> можно предположить, что <tex>k\leqslant t<=t/tex>. Первые <tex>t-k+2</tex> уровней разделяются на <tex>2^{k-2}</tex> отдельных сетей размеров <tex>2^{t-k+2}</tex>, каждая из которых является <tex>2</tex>-упорядоченной в случае <tex>k=2</tex>; следовательно, линии являются <tex>2^{k-1}</tex>-упорядоченными после <tex>t-k+2</tex> уровней. Последующие уровни, очевидно, сохраняют <tex>2^{k-1}</tex>-упорядоченность, так как они обладают "вертикальной" периодичностью порядка <tex>2^{k-2}</tex>.