Lower Bounds on Merging Networks

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].