Periodic Sorting on Two-Dimensional Meshes
Kutylowski, Miroslaw
Wanka, Rolf
We consider the following periodic sorting procedure on two-dimensional meshes of processors: Initially, each node contains one number. We proceed in rounds each round consisting of sorting the columns of the grid, and, in the second phase, of sorting the rows according to the snake-like ordering. We exactly characterize the number of rounds necessary to sort on an l × m-grid in the worst case, where l is the number of the rows and m the number of the columns. An upper bound of ⌈ log l⌉ + 1was known before. This bound is tight for the case that m is not a power of 2. Surprisingly, it turns out that far fewer rounds are necessary if m is a power of 2 (and m ≪ l) in this case, exactly min { log m + 1, ⌈ log l⌉ + 1} rounds are needed in the worst case.
1992
info:eu-repo/semantics/article
doc-type:article
text
http://purl.org/coar/resource_type/c_6501
https://ris.uni-paderborn.de/record/18936
Kutylowski M, Wanka R. Periodic Sorting on Two-Dimensional Meshes. <i>Parallel Processing Letters 2</i>. Published online 1992:213-220. doi:<a href="https://doi.org/10.1142/s0129626492000349">10.1142/s0129626492000349</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1142/s0129626492000349
info:eu-repo/semantics/altIdentifier/issn/0129-6264
info:eu-repo/semantics/altIdentifier/issn/1793-642X
info:eu-repo/semantics/closedAccess