Изменения

Воспользуемся Определим операцию вложения компаратора <tex> [i:j] </tex> в компаратор <tex> [t:s] </tex>. Для этого разместим компаратор <tex> [i:j] </tex> и <tex> [t:s] </tex> на одном слое, так, что <tex> t < i < j < s </tex>. Теперь воспользуемся принципом математической индукции.

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