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

Hilfe Wegweiser Impressum Kontakt Einloggen

# Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

#### Improved parallel integer sorting without concurrent writing

##### MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons43989

Albers,  Susanne
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44564

Hagerup,  Torben
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
##### Volltexte (frei zugänglich)

MPI-I-94-137.pdf
(beliebiger Volltext), 17MB

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

Albers, S., & Hagerup, T.(1994). Improved parallel integer sorting without concurrent writing (MPI-I-94-137). Saarbrücken: Max-Planck-Institut für Informatik.

We show that $n$ integers in the range $1 \twodots n$ can be stably sorted on an \linebreak EREW PRAM using \nolinebreak $O(t)$ time \linebreak and $O(n(\sqrt{\log n\log\log n}+{{(\log n)^2}/t}))$ operations, for arbitrary given \linebreak $t\ge\log n\log\log n$, and on a CREW PRAM using %$O(\log n\log\log n)$ time and $O(n\sqrt{\log n})$ $O(t)$ time and $O(n(\sqrt{\log n}+{{\log n}/{2^{{t/{\log n}}}}}))$ operations, for arbitrary given $t\ge\log n$. In addition, we are able to sort $n$ arbitrary integers on a randomized CREW PRAM % using %$O(\log n\log\log n)$ time and $O(n\sqrt{\log n})$ operations within the same resource bounds with high probability. In each case our algorithm is a factor of almost $\Theta(\sqrt{\log n})$ closer to optimality than all previous algorithms for the stated problem in the stated model, and our third result matches the operation count of the best known sequential algorithm. We also show that $n$ integers in the range $1 \twodots m$ can be sorted in $O((\log n)^2)$ time with $O(n)$ operations on an EREW PRAM using a nonstandard word length of $O(\log n \log\log n \log m)$ bits, thereby greatly improving the upper bound on the word length necessary to sort integers with a linear time-processor product, even sequentially. Our algorithms were inspired by, and in one case directly use, the fusion trees of Fredman and Willard.