BOUNDS ON THE SIZE OF MERGING NETWORKS

Let M(m,n) be the minimum number of comparators needed in an (m,n)-mer ging network. Batcher's odd-even merge provides upper bounds, whereas the best general lower bounds were established by Yao and Yao (1976) a nd Miltersen et al. (to appear). In this paper, we concentrate on smal l fixed m and arbitrary n. M(1,n) = n has long been known. In their 19 76 paper, Yao and Yao showed M(2,n) = [3n/2] and asked for the exact v alue of M(3,n). We prove M(3,n) = [(7n + 3)/4] for all n. Furthermore, M(4,n) > 11/6n, M(5,n) > 2n are shown, improving previous bounds. Som e related questions are discussed.