I'm trying to answer clrs intro to alg edition2 exercises. in chapter 27.1-4 there is an exercise which says: "Prove that any sorting network on n inputs has depth at least lg n". so I think that we can use at most (n/2) comparators in each depth and if we assume that we have found a combination of comparators which can sort (n/2) of the numbers in depth1 then we need to sort the other (n/2) of the numbers. So if we keep doing the same thing we're dividing n by two in each depth so the depth of the sorting network would be lgn. Is this conclusion wrong? if it is what is the right way of proving the lower bound of a sorting networks depth.
1 Answers
I can think of two.
The first is that you can view a sorting network for n elements as a comparison-based sorting algorithm, and the lower bound on the latter implies that the network does lg n! = n lg n − n + O(log n) comparisons, divided by n/2 comparisons per level is 2 lg n − 1 + O((log n)/n) ≥ lg n if n ≥ 2 (and you can verify n = 1 manually).
The other is that after r rounds, each input can have been shuffled to at most 2r different locations. This can be proved by induction. Each input must be able to reach each output, so 2r ≥ n, which implies r ≥ lg n.
(Better to ask this kind of question on cs.stackexchange.com in the future.)
Related