hide
Free keywords:
-
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.
