Playing Tetris on Meshes and Multi-Dimensional Shearsort

TitlePlaying Tetris on Meshes and Multi-Dimensional Shearsort
Publication TypeTechnical Report
Year of Publication1997
AuthorsKutylowski, M., & Wanka R.
Other Numbers1094

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 x l x l-mesh, it suffices to perform 2 log l + 10 rounds while 2 log l + 1 rounds are necessary. Moreover, tools for analyzing multi-dimensional Shearsort are provided.

Bibliographic Notes

ICSI Technical Report TR-97-029

Abbreviated Authors

M. Kutylowski and R. Wanka

ICSI Publication Type

Technical Report