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. Experiments on random inputs indicate that multi-dimensional Shearsort may satisfy similar time bounds as its 2-dimensional counterpart. In this paper, we present an analysis of the 3-dimensional case and show that on the cube with side length l, 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.