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 p ermutation. We prove Eight 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 Th eta(n log log n) on the size of networks of success probability in [de lta, 1-1/poly(n)], where delta is an arbitrarily small positive consta nt, thus comparing favorably with the best previously known solutions; which have size Theta(n log n). We also prove tight bounds, up to low er-order terms, on the size and depth of probabilistic merging network s of success probability in [delta, 1-1 /poly(n)], where delta is an a rbitrarily small positive constant. Finally, we describe two fairly si mple probabilistic sorting networks of success probability at least 1- 1/poly(n) and nearly logarithmic depth.