@inproceedings{6402f99de1fd4c359d29b3266978c4d9,
title = "Sorting within distance bound on a mesh-connected processor array",
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.",
author = "Chlebus, {Bogdan S.}",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1989.; 2nd International Symposium on Optimal Algorithms, 1989 ; Conference date: 29-05-1989 Through 02-06-1989",
year = "1989",
doi = "10.1007/3-540-51859-2_18",
language = "English (US)",
isbn = "9783540518594",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "232--238",
editor = "Hristo Djidjev",
booktitle = "Optimal Algorithms - International Symposium, Proceedings",
}