## Periodic Sorting on Two-Dimensional Meshes

Miroslaw Kutylowski, Rolf Wanka

Dept. of Mathematics and Computer Science

and Heinz Nixdorf Institute

Paderborn University

D-33095 Paderborn, Germany

e-mail: {mirekk, wanka}@uni-paderborn.de

## 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, wherelis the number of the rows andmthe number of the columns. An upper bound ofceil(log was known before. This bound is tight for the case thatl)+1mis not a power of 2. Surprisingly, it turns out that far fewer rounds are necessary ifmis a power of 2 (and: in this case, exactly m«l)min{ log rounds are needed in the worst case.m+ 1, ceil(logl) + 1}

Full paperin Postscript format.© Copyright 1992 World Scientific Publishing Company. Published in

Parallel Processing Letters2 (1992) 213-220.