# Item

ITEM ACTIONSEXPORT

Released

Report

#### Desnakification of mesh sorting algorithms

##### Locator

There are no locators available

##### Fulltext (public)

MPI-I-94-102.pdf

(Any fulltext), 224KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Sibeyn, J. F.(1994). *Desnakification of mesh sorting algorithms*
(MPI-I-94-102). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-B4FC-3

##### Abstract

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.