A superlogarithmic lower bound for shuffle-unshuffle sorting networks

C. G. Plaxton, T. Suel

    Research output: Contribution to journalArticle

    Abstract

    Shuffle-unshuffle sorting networks are a class of comparator networks whose structure maps efficiently to the hypercube and any of its bounded degree variants. Recently, n-input shuffle-unshuffle sorting networks with depth 2O(√lg lg n) lg n have been discovered. These networks are the only known sorting networks of depth o(lg2 n) that are not based on expanders, and their existence raises the question of whether a depth of O (lg n) can be achieved by any shuffle-unshuffle sorting network. In this paper we resolve this question by establishing an Ω (lg n lg lg n/lg lg lg n) lower bound on the depth of any n-input shuffle-unshuffle sorting network. Our lower bound can be extended to certain restricted classes of nonoblivious sorting algorithms on hypercubic machines.

    Original languageEnglish (US)
    Pages (from-to)233-254
    Number of pages22
    JournalTheory of Computing Systems
    Volume33
    Issue number3
    DOIs
    StatePublished - 2000

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computational Theory and Mathematics

    Fingerprint Dive into the research topics of 'A superlogarithmic lower bound for shuffle-unshuffle sorting networks'. Together they form a unique fingerprint.

    Cite this