We prove an Ω(lg2n/lg lg n) lower bound for the depth of n-input sorting networks based on the shuffle permutation. The best previously known lower bound was the trivial Ω(lg n) bound, while the best upper bound is given by Batcher's Θ(lg2n)-depth bitonic sorting network. The proof technique employed in the lower bound argument may be of independent interest.
ASJC Scopus subject areas
- Theoretical Computer Science
- Computational Theory and Mathematics