---
res:
bibo_abstract:
- '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.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Miroslaw
foaf_name: Kutylowski, Miroslaw
foaf_surname: Kutylowski
- foaf_Person:
foaf_givenName: Rolf
foaf_name: Wanka, Rolf
foaf_surname: Wanka
bibo_doi: 10.1142/s0129626492000349
dct_date: 1992^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/0129-6264
- http://id.crossref.org/issn/1793-642X
dct_language: eng
dct_title: Periodic Sorting on Two-Dimensional Meshes@
...