Изменения

При переходе от сортирующей сети с <tex>n</tex> входами к сети с <tex>n + 1</tex> входами, добавляем <tex> n </tex> компаратор<tex>\left( [0:1] \dots [0:n]\right) </tex>. Заметим, что в <tex> n - 2 </tex> добавленных компараторов я могу можно вложить <tex> n - 2 </tex> компараторов из предыдущей сети, так, что условие слоя не нарушатся. Тогда останется два компаратора: <tex>[0:1], [0:2] </tex> в которые я ничего не могу нельзя вложить, чтобы не нарушить условие вложения. Тогда количество слоев изменяется на <tex> 2 </tex>. Однако, начиная с <tex> n = 4 </tex> можно перенести свободные компараторы и слить их в один слой, но при этом сеть перестает быть сортирующей (при <tex> n = 4 </tex> ошибка будет возникать на векторе <tex> 0100 </tex>). Тем самым получили рекуррентное соотношение: