# 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.pdf | 239 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},`

`}`