MPI-INF/SWS Research Reports 1991-2021

2. Number - only D1


Desnakification of mesh sorting algorithms

Sibeyn, Jop F.

January 1994, 21 pages.

Status: available - back from printing

In all recent near-optimal sorting algorithms for meshes, the packets are sorted with respect to some snake-like indexing. Such algorithms are useless in many practical applications. In this paper we present deterministic algorithms for sorting with respect to the more natural row-major indexing. For 1-1 sorting on an $n \times n$ mesh, we give an algorithm that runs in $2 \cdot n + o(n)$ steps, with maximal queue size five. It is considerably simpler than earlier algorithms. Another algorithm performs $k$-$k$ sorting in $k \cdot n / 2 + o(k \cdot n)$ steps. Furthermore, we present {\em uni-axial} algorithms for row-major sorting. Uni-axial algorithms have clear practical and theoretical advantages over bi-axial algorithms. We show that 1-1 sorting can be performed in $2\frac{1}{2} \cdot n + o(n)$ steps. Alternatively, this problem is solved in $4\frac{1}{3} \cdot n$ steps for {\em all $n$}. For the practically important values of $n$, this algorithm is much faster than any algorithm with good {\em asymptotical} performance.
Categories / Keywords:

  • Attachement: (239 KBytes); MPI-I-94-102.pdf (223 KBytes)

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Sibeyn, Jop F.},
  TITLE = {Desnakification of mesh sorting algorithms},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-94-102},
  MONTH = {January},
  YEAR = {1994},
  ISSN = {0946-011X},