Изменения

Эти идеальные разделители могут быть использованы как модули для построения сортирующей сети на <tex>N</tex> входов, где <tex>N = k^d</tex> для некоторого положительного числа d. Такая сеть будет представлять собой композицию сетей <tex>N_0, N_1, N_2 .. \dots N_{d-1}</tex>, где <tex>N_t</tex> – парраллельная композиция <tex>k^t</tex> идеальных разделителей одинакового размера. <tex>k^{d - t}</tex> Выходных проводов уровня <tex>N_t</tex> разделены на <tex>k</tex> блоков одинакового размерв и каждый из этих блоков формирует вход для идеального разделителя из N_{t+1}.Можно рассмотреть другую интерпретацию этой конструкции. k^d входных данных мы будем рассматривать как листья полного k-ичного дерева глубины d; каждый модуль(разделитель) из N_t будем считать узлом, находящимся на высоте t в нашем дереве. Будем считать, что в каждый момент времени t = 0, 1, 2, ... в - 1 входные провода распределены по всему уровню t нашего дерева. В то же время, каждый узел х на t уровне принимает k^{d - t} проводов и эти провода затем используются как вход для идеального разделителя который разбивает их на k блоков одинакового размера в промежуток времени между t и t + 1. Выходные провода из j получившегося блока идут в j ребенка вершины x. К моменту времени d каждый лист дерева содершит в себе только один провод, а этот провод содержит в себе значение, которое и приписывается к листу.

К сожалению, эта схема описывает сортирующую сеть глубины <tex>\alpha^*Omega(t(\log_k N) = (\frac{tlog_m N)) </tex>: каждый идеальный разделитель на а проводов, если его делать из М-разделителей, должен иметь глубину более чем <tex>\log log_M(\fracdfrac{k-1}{\nuk} - \log N + \loga). (2AЧтобы осознать это, заметим, что для каждого выхода y должно быть более чем <tex>\nu dfrac{k^3)-1}{k}a</tex> входов x , таких, что ключ мог бы дойти от x до y). К счастью, схему можно переделать так, чтобы она описывала сортирующую сеть глубины <tex>O(\log A}log_M N)</tex>: идеальные разделители можно заменить на более слабые модули константной глубины,чья слабость будет компенсироваться более сложным перемещением ключей через дерево.

Слабые модули мы назовем сепараторами. У каждого такого сепаратора есть а выходных проводов, которые делятся на блоки <tex>F_1, B_1, B_2, \omega^*(t) dots, B_k, F_2 </tex> так, что <tex> |F_1| = |F_2|</tex> <tex> |B_1| = |B_2| = \frac{t\log \frac{1}{\nu} + \log(A\nu k)}{\log Ak}dots = |B_k| </tex>;

<tex>\alpha(t) \ge \alpha^*(t)Как правило,\quad \alpha(t)\equiv t\; mod\; 2 </tex>  "обрамляющие блоки" <tex>\omega(t) \ge \omega^*(t),\quad \omega(t)\equiv t\; mod\; 2 F_1</tex>  и <tex> O(\log N) F_2</tex> <tex> c\log_2 N </tex> <tex> \pi(\alpha(t),t) =\begin{cases}0,&\text{если $\alpha(t + 1)>\alpha(t)$,}\\\frac{\nu}{AK}c(a(t),t), &\text{если $\alpha(t + 1)>\alpha(t)$гораздо меньше всех остальных.}\end{cases}</tex> <tex> \pi(i,t) = \frac{A\nu k В каком- 1}{A^2k^2}c(iто смысле,t)можно сказать,\quad \text{если $\alpha(t) < i < \omega(t)$,}</tex> <tex> \pi(\omega(t),t) =\begin{cases}\frac{A\nu k - 1}{A^2k^2}c(\omega(t),t),&\text{ $\omega(t + 1)>\omega(t)$,}\\\alpha(\omega(t),t),&\text{если $\omega(t + 1)<\omega(t)$,}\end{cases}</tex>что сепаратор аппроксимирует идеальный разделитель.