Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


Improved parallel integer sorting without concurrent writing

Albers, Susanne and Hagerup, Torben

MPI-I-94-137. July 1994, ? pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.
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-137.pdfMPI-I-94-137.pdf17166 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:
Hide details for BibTeXBibTeX
  AUTHOR = {Albers, Susanne and Hagerup, Torben},
  TITLE = {Improved parallel integer sorting without concurrent writing},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-94-137},
  MONTH = {July},
  YEAR = {1994},
  ISSN = {0946-011X},