# Item

ITEM ACTIONSEXPORT

Released

Report

#### Improved parallel integer sorting without concurrent writing

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

MPI-I-94-137.pdf

(Any fulltext), 17MB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

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

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

##### Abstract

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.