On Probabilistic Networks for Selection, Merging, and Sorting

We study comparator networks for selection, merging, and sorting that output the correct result with high probability, given a random input permutation. We prove tight bounds, up to constant factors, on the size and depth of probabilistic (n,k)-selection networks. In the case of (n, n/2)-selection, our result gives a somewhat surprising bound of on the size of networks of success probability in , where δ is an arbitrarily small positive constant, thus comparing favorably with the best previously known solutions, which have size . We also prove tight bounds, up to lower-order terms, on the size and depth of probabilistic merging networks of success probability in , where δ is an arbitrarily small positive constant. Finally, we describe two fairly simple probabilistic sorting networks of success probability at least and nearly logarithmic depth. Received January 22, 1996, and in final form February 14, 1997.