Изменения

== Введение ==Ажтаи (Ajtai), Комлос (Komlos) и Шимереди (Szemeredi) сконструировали сортирующую сеть на N входов глубины <tex> O(nlogn\log N). Они </tex>, при они не соседотачивались на значении углублялись в исследование значения константы, скрытой в O-нотацииполучавшейся при правильном соблюдении необходимой ассимптотики. Впоследствии Патерсон заменил выяснил, что <tex> O(logn\log N) </tex> можно заменить на clog(n, 2) <tex> c\log_2 N </tex> с константой приблизительно равной <tex> 6100</tex>. Здесь будет описана более поздняя реализация, которая включает в себя меньшую константу с : <tex>c</tex>, а именно, будет доказано, что для любого целого числа <tex>N </tex> такого,что <tex>N >= \ge 2 ^ {78 }</tex> существует сортирующая сеть на <tex>N </tex> входов, такая, что глубина в худшем случае будет <tex>1830 * log(\log_2 N, 2) – - 58657</tex>.

Основными составяющими этой конструкции будут сортирующие сети на <tex>M </tex> входов, такие ,что <tex>M </tex> относительно мало. Мы назовем их <tex>M</tex>-сортировщиками. Для любых выбранных положительных целых чисел <tex>M </tex> и <tex>N </tex> таких что <tex> N \ge M</tex>= M, конструкция будет включать в себя <tex>N </tex> проводов, и будет сделана из <tex>M</tex>-сортировщиков, глубина которых в худшем случае <tex>(48 + о(1))log(N, M) \log_MN + 115 </tex> при <tex>M → \to \inf</tex>.(Стоит подчеркнутьотметить, что асимптотическое о<tex>o(1) </tex> здесь по отношению относится к М<tex>M</tex>, а не к <tex>N</tex>).

== Сепараторы Разделители ==

<tex>\alpha^*(t) = \frac{t\log \frac{1}{\nu} - \log N + \log(2A\nu k^3)}{\log A}</tex> <tex>\omega^*(t) = \frac{t\log \frac{1}{\nu} + \log(A\nu k)}{\log Ak}</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 </tex>  <tex> O(logN\log N) </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>