Участник:Dominica

Введение

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

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

Сепараторы

Сначала введем все необходимые понятия для построения сортирующей сети.

[math] O(logN) [/math]