Lower bound for sorting networks based on the shuffle permutation

C. Greg Plaxton; Torsten Suel

Lower bound for sorting networks based on the shuffle permutation

C. Greg Plaxton, Torsten Suel

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We prove an Ω(lg² 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 language	English (US)
Title of host publication	4th Annual ACM Symposium on Parallel Algorithms and Architectures
Publisher	Publ by ACM
Pages	70-79
Number of pages	10
ISBN (Print)	089791483X
State	Published - 1992
Event	4th Annual ACM Symposium on Parallel Algorithms and Architectures - SPAA '92 - San Diego, CA, USA Duration: Jun 29 1992 → Jul 1 1992

Publication series

Name	4th Annual ACM Symposium on Parallel Algorithms and Architectures

Other

Other	4th Annual ACM Symposium on Parallel Algorithms and Architectures - SPAA '92
City	San Diego, CA, USA
Period	6/29/92 → 7/1/92

ASJC Scopus subject areas

General Engineering

Cite this

@inproceedings{592f4ea53c8a4985bf2e68e64611bb8f,

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

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

author = "Plaxton, {C. Greg} and Torsten Suel",

year = "1992",

language = "English (US)",

isbn = "089791483X",

series = "4th Annual ACM Symposium on Parallel Algorithms and Architectures",

publisher = "Publ by ACM",

pages = "70--79",

booktitle = "4th Annual ACM Symposium on Parallel Algorithms and Architectures",

note = "4th Annual ACM Symposium on Parallel Algorithms and Architectures - SPAA '92 ; Conference date: 29-06-1992 Through 01-07-1992",

}

TY - GEN

T1 - Lower bound for sorting networks based on the shuffle permutation

AU - Plaxton, C. Greg

AU - Suel, Torsten

PY - 1992

Y1 - 1992

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

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

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

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

M3 - Conference contribution

AN - SCOPUS:0026965898

SN - 089791483X

T3 - 4th Annual ACM Symposium on Parallel Algorithms and Architectures

SP - 70

EP - 79

BT - 4th Annual ACM Symposium on Parallel Algorithms and Architectures

PB - Publ by ACM

T2 - 4th Annual ACM Symposium on Parallel Algorithms and Architectures - SPAA '92

Y2 - 29 June 1992 through 1 July 1992

ER -

Lower bound for sorting networks based on the shuffle permutation

Abstract

Publication series

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this