An Improved Lower Bound for Sorting Networks
- 1 June 1972
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-21 (6) , 612-613
- https://doi.org/10.1109/tc.1972.5009021
Abstract
The minimum number of comparators S(N) required by an N-input sorting network is bounded below by S(N) ≥ N[log2 (N) - 1] + 0(1), as a consequence of the theorem S(N) ≥ S(N - 1) + [log2 (N)].Keywords
This publication has 1 reference indexed in Scilit:
- A Sorting ProblemJournal of the ACM, 1962