max planck institut
informatik

MPI-I-94-102

Desnakification of mesh sorting algorithms

Sibeyn, Jop F.

MPI-I-94-102. January 1994, 21 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.
Acknowledgement:
Categories / Keywords: sorting
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-94-102.pdf239 KBytes; 223 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1994-102
BibTeX
@TECHREPORT{Sibeyn94,
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},
}