Sorting within distance bound on a mesh-connected processor array
Scholary Output:
Chapter in Book/Report/Conference proceeding
Conference contribution
Related Event
Title
2nd International Symposium on Optimal Algorithms, 1989
Event type
ConferenceDate
05/29/1989 - 06/02/1989Location
VarnaBulgaria
Abstract
An algorithm is developed which sorts random sequences of keys on the n × n square mesh in the expected time 2n. The algorithm is shown to be optimal, that is, the matching Ω(2n) lower bound on the expected-time of algorithms sorting randomly ordered inputs is proved.
Publication Information
Output type
Scholary Output:
Chapter in Book/Report/Conference proceeding
Conference contribution
Original language
English (US)Pages from-to (Number of pages)
Pages 232-238 (7 pages)Publication milestones
- Published - 1989
Publication status
Published - 1989
Publisher
Springer VerlagPublication series
- Publication series name: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print): 0302-9743
ISSN (Electronic): 1611-3349
Volume: 401 LNCS
ISBN (Print)
9783540518594Publication IDs
- Scopus: 84941529229
Host publication title
Optimal Algorithms - International Symposium, ProceedingsHost publication editors
- Hristo Djidjev
Publication metrics
Metrics
Fractional count
1
Fractional count
1
Fractional count
1
Fractional count
1
PlumX, opens in new tab
Captures
1
Citation count
5