Lower bound for sorting networks based on the shuffle permutation

C. Greg Plaxton, Torsten Suel

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    We prove an Ω(lg2 n/lg lg n) lower bound for the depth of sorting networks based on the shuffle permutation. This settles an open question posed by Knuth, up to a Θ(lg lg n) factor. The proof technique employed in the lower bound argument may be of separate interest.

    Original languageEnglish (US)
    Title of host publication4th Annual ACM Symposium on Parallel Algorithms and Architectures
    PublisherPubl by ACM
    Pages70-79
    Number of pages10
    ISBN (Print)089791483X
    StatePublished - 1992
    Event4th Annual ACM Symposium on Parallel Algorithms and Architectures - SPAA '92 - San Diego, CA, USA
    Duration: Jun 29 1992Jul 1 1992

    Publication series

    Name4th Annual ACM Symposium on Parallel Algorithms and Architectures

    Other

    Other4th Annual ACM Symposium on Parallel Algorithms and Architectures - SPAA '92
    CitySan Diego, CA, USA
    Period6/29/927/1/92

    ASJC Scopus subject areas

    • Engineering(all)

    Fingerprint Dive into the research topics of 'Lower bound for sorting networks based on the shuffle permutation'. Together they form a unique fingerprint.

    Cite this