On probabilistic networks for selection, merging, and sorting

T. Leighton, Y. Ma, T. Suel

    Research output: Contribution to journalArticlepeer-review

    Abstract

    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 Θ(n log log n) on the size of networks of success probability in [δ, 1 - 1/poly (n)], where δ is an arbitrarily small positive constant, thus comparing favorably with the best previously known solutions, which have size Θ(n log n). We also prove tight bounds, up to lower-order terms, on the size and depth of probabilistic merging networks of success probability in [δ, 1 - 1/poly(n)], where δ is an arbitrarily small positive constant. Finally, we describe two fairly simple probabilistic sorting networks of success probability at least 1 - 1/poly(n) and nearly logarithmic depth.

    Original languageEnglish (US)
    Pages (from-to)559-582
    Number of pages24
    JournalTheory of Computing Systems
    Volume30
    Issue number6
    DOIs
    StatePublished - 1997

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computational Theory and Mathematics

    Fingerprint Dive into the research topics of 'On probabilistic networks for selection, merging, and sorting'. Together they form a unique fingerprint.

    Cite this