A LOWER-BOUND FOR SORTING NETWORKS BASED ON THE SHUFFLE PERMUTATION

Authors
PLAXTON CG SUEL T
Citation
Cg. Plaxton et T. Suel, A LOWER-BOUND FOR SORTING NETWORKS BASED ON THE SHUFFLE PERMUTATION, Mathematical systems theory, 27(5), 1994, pp. 491-508
Citations number
15
Categorie Soggetti
System Science","Mathematics, Pure","Computer Science Theory & Methods",Mathematics
Journal title
Mathematical systems theory → ACNP
ISSN journal
00255661
Volume
27
Issue
5
Year of publication
1994
Pages
491 - 508
Database
ISI
SICI code
0025-5661(1994)27:5<491:ALFSNB>2.0.ZU;2-E
Abstract
We prove an OMEGA(lg2 n/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 OMEGA(lg n) bound, while the best u pper bound is given by Batcher's THETA(lg2 n)-depth bitonic sorting ne twork. The proof technique employed in the lower bound argument may be of independent interest.