Изменения

Оценим глубину этой сортирующей сети. Она состоит из <tex>\log_2{n}</tex> слоёв объединяющих сетей и каждый слой имеет глубину, зависящую от его номера. В слое с номером <tex>i</tex> (<tex>1 \leqslant i \leqslant \log_2{n}</tex>) объединяющая сеть имеет глубину <tex>\log_2{2^i}</tex>, потому как объединяет <tex>2^i</tex> проводов. Таким образом глубина всей сортирующей сети в точности равна <tex dpi = "150">\sum\limits^{\log_2{n}}_{i = 1}{\log_2{2^i}} = \sum\limits^{\log_2{n}}_{i = 1}{i} = \fracdfrac{(1+\log_2{n})\log_2{n}}{2}</tex>.

Оценим размер сети. В объединяющей сети на <tex>n</tex> входов содержится <tex dpi="150">\fracdfrac{n \log_2{n}}{2}</tex> компараторов. Снова просуммируем формулу по числу объединяющих сетей и получим точную оценку <tex dpi = "150">\sum\limits^{\log_2{n}}_{i = 1}{ \fracdfrac{2^i \log_2{2^i}}{2} } = \sum\limits^{\log_2{n}}_{i = 1}{ 2^{i-1} i} = \fracdfrac{n \log_{2}^{2}{n} + 2 \log_2{n}}{4}</tex>.