Изменения

Нуль-единичные битонические последовательности - последовательности вида <tex>0^i1^j0^k</tex> или <tex>1^i0^j1^k</tex> для <tex>i,j,k\le0</tex>}}

На первом этапе конструирования стоит задача построить сравнивающую сеть, которая будет сортировать любую нуль-единичную битоническую последовательность - битонический сортировщик.

Битонический сортировщик состоит из нескольких каскадов, каждый из которых называется <b>''полуфильтром''</b> (half-cleaner). Каждый полуфильтр - сравнивающая сеть глубиной 1, в которой <tex>i</tex>-й входной провод сравнивается со входным проводом с номером <tex>i+\frac{n}{2}</tex>, где <tex>i=1,2,...,\frac{n}{2}</tex>.<br>

{{Лемма|statement=