Publication Details
Title: Playing Tetris on Meshes and Multi-Dimensional Shearsort
Author: M. Kutylowski and R. Wanka
Group: ICSI Technical Reports
Date: August 1997
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1997/tr-97-029.pdf
Overview:
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 Information:
ICSI Technical Report TR-97-029
Bibliographic Reference:
M. Kutylowski and R. Wanka. Playing Tetris on Meshes and Multi-Dimensional Shearsort. ICSI Technical Report TR-97-029, August 1997
Author: M. Kutylowski and R. Wanka
Group: ICSI Technical Reports
Date: August 1997
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1997/tr-97-029.pdf
Overview:
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 Information:
ICSI Technical Report TR-97-029
Bibliographic Reference:
M. Kutylowski and R. Wanka. Playing Tetris on Meshes and Multi-Dimensional Shearsort. ICSI Technical Report TR-97-029, August 1997