MPII94102
Desnakification of mesh sorting algorithms
Sibeyn, Jop F.
January 1994, 21 pages.
.
Status: available  back from printing
In all recent nearoptimal sorting algorithms for meshes, the
packets are sorted with respect to some snakelike indexing. Such
algorithms are useless in many practical applications. In this
paper we present deterministic algorithms for sorting with respect
to the more natural rowmajor indexing.
For 11 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 uniaxial} algorithms for rowmajor
sorting. Uniaxial algorithms have clear practical and theoretical
advantages over biaxial algorithms. We show that 11 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:
sorting

MPII94102.pdf
 Attachement: MPII94102.ps (239 KBytes); MPII94102.pdf (223 KBytes)
URL to this document: https://domino.mpiinf.mpg.de/internet/reports.nsf/NumberView/1994102
BibTeX
@TECHREPORT{Sibeyn94,
AUTHOR = {Sibeyn, Jop F.},
TITLE = {Desnakification of mesh sorting algorithms},
TYPE = {Research Report},
INSTITUTION = {MaxPlanckInstitut f{\"u}r Informatik},
ADDRESS = {Im Stadtwald, D66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPII94102},
MONTH = {January},
YEAR = {1994},
ISSN = {0946011X},
}