Playing Tetris on Meshes and Multi-Dimensional SHEARSORT
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
Shearsort is a classical sorting algorithm working in rounds on 2-dimensional meshes of processors. Its elementary and elegant runtime analysis can be found in various textbooks. There is a straightforward generalization of Shearsort to multi-dimensional meshes. As experiments turn out, it works fast. However, no method has yet been shown strong enough to provide a tight analysis of this algorithm. In this paper, we present an analysis of the 3-dimensional case and show that on the
l×l×l-mesh, it suffices to perform2 log l + 10 rounds while2 log l + 1 rounds are necessary. Moreover, tools for analyzing multi-dimensional Shearsort are provided.
Paper in compressed Postscript format (gzip used):
A4 format US letter format © Copyright 1997 Springer-Verlag. Published in the Proceedings of the 8th International Symposium on Algorithms and Computation (ISAAC), pp. 31-42, 1997.