| 3 (2007) | |||||||||||||||
Abstract | |||||||||||||||
| 7 We establish a lower bound of (1:12 \Gamma o(1)) n log n on the size of any n-input sorting network; this is the first lower bound that improves upon the trivial information-theoretic bound by more than a lower order term. We then extend the lower bound to comparator networks that approximately sort a certain fraction of all input permutations. We also prove a lower bound of (c \Gamma o(1)) log n, where c 3:27, on the depth of any sorting network; the best previous result of approximately (2:41 \Gamma o(1)) log n was established by Yao in 1980. Our result for size is based on a new technique that lower bounds the number of "0--1 collisions " in the network; we provide strong evidence that the technique will lead to even better lower bounds. 1 Part of this work was done while the author was at DIMACS. | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||