Lower Bounds on Merging Networks
Open Access
- 1 July 1976
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 23 (3) , 566-571
- https://doi.org/10.1145/321958.321976
Abstract
Let M ( m, n ) be the minimum number or comparators needed in an ( m, n )-merging network. It is shown that M ( m, n ) ≥ n (lg( m + 1))/2, which implies that Batcher's merging networks are optimal up to a factor of 2 + ε for almost all values of m and n . The limit r m = lim n→∞ M ( m, n )/ n is determined to within 1. It is also proved that M (2, n ) = [3 n /2].Keywords
This publication has 1 reference indexed in Scilit:
- Permuting Information in Idealized Two-Level StoragePublished by Springer Nature ,1972