A lower bound for sorting networks based on the shuffle permutation

C. G. Plaxton; T. Suel

doi:10.1007/BF01184936

A lower bound for sorting networks based on the shuffle permutation

C. G. Plaxton, T. Suel

Research output: Contribution to journal › Article › peer-review

Abstract

We prove an Ω(lg²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 Ω(lg n) bound, while the best upper bound is given by Batcher's Θ(lg²n)-depth bitonic sorting network. The proof technique employed in the lower bound argument may be of independent interest.

Original language	English (US)
Pages (from-to)	491-508
Number of pages	18
Journal	Mathematical Systems Theory
Volume	27
Issue number	5
DOIs	https://doi.org/10.1007/BF01184936
State	Published - Sep 1994

ASJC Scopus subject areas

Theoretical Computer Science
General Mathematics
Computational Theory and Mathematics

Access to Document

10.1007/BF01184936

Cite this

@article{cf30a5f0ae2c4dcd909acf9d104b12df,

title = "A lower bound for sorting networks based on the shuffle permutation",

abstract = "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.",

author = "Plaxton, {C. G.} and T. Suel",

year = "1994",

month = sep,

doi = "10.1007/BF01184936",

language = "English (US)",

volume = "27",

pages = "491--508",

journal = "Mathematical Systems Theory",

issn = "0025-5661",

publisher = "Springer New York",

number = "5",

}

TY - JOUR

T1 - A lower bound for sorting networks based on the shuffle permutation

AU - Plaxton, C. G.

AU - Suel, T.

PY - 1994/9

Y1 - 1994/9

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0039163195&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0039163195&partnerID=8YFLogxK

U2 - 10.1007/BF01184936

DO - 10.1007/BF01184936

M3 - Article

AN - SCOPUS:0039163195

SN - 0025-5661

VL - 27

SP - 491

EP - 508

JO - Mathematical Systems Theory

JF - Mathematical Systems Theory

IS - 5

ER -

A lower bound for sorting networks based on the shuffle permutation

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this