de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch

Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt

# Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Zeitschriftenartikel

#### Row-Major Sorting on Meshes

##### MPG-Autoren

Sibeyn,  Jop F.
Max Planck Society;

##### Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
##### Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
##### Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
##### Zitation

Sibeyn, J. F. (1999). Row-Major Sorting on Meshes. SIAM Journal on Computing, 28(3), 847-863.

In all recent near-optimal sorting algorithms for meshes, the packets are sorted with respect to some snake-like indexing. 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, matching the distance bound, 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, matching the bisection bound. Furthermore, we present {\em uni-axial} algorithms for row-major sorting. We show that 1-1 sorting can be performed in $2\breukk{1}{2} \cdot n + o(n)$ steps. Alternatively, this problem is solved with maximal queue size five in $4\breukk{1}{3} \cdot n$ steps, without any additional terms.