 max planck institut
informatik MPI-I-93-123

Fast parallel space allocation, estimation and integer sorting (revised)

Bast, Holger and Hagerup, Torben

MPI-I-93-123. June 1993, 85 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
The following problems are shown to be solvable
in $O(\log^{\ast }\! n)$ time
with optimal speedup with high probability on a
randomized CRCW PRAM using
$O(n)$ space:
\begin{itemize}
\item
Space allocation: Given $n$ nonnegative integers
$x_1,\ldots,x_n$, allocate $n$ nonoverlapping
blocks of consecutive
memory cells of sizes $x_1,\ldots,x_n$ from a base
segment of $O(\sum_{j=1}^n x_j)$ consecutive
memory cells;
\item
Estimation: Given $n$ integers %$x_1,\ldots,x_n$
in the range $1.. n$, compute good'' estimates
of the number of occurrences of each value
in the range $1.. n$;
\item
Semisorting: Given $n$ integers $x_1,\ldots,x_n$
in the range $1.. n$,
store the integers $1,\ldots,n$ in an array of $O(n)$
cells such that for all $i\in\{1,\ldots,n\}$,
all elements of $\{j:1\le j\le n$ and $x_j=i\}$
occur together, separated only by empty cells;
\item
Integer chain-sorting: Given $n$ integers $x_1,\ldots,x_n$
in the range $1.. n$, construct a linked list
containing the integers $1,\ldots,n$ such that for all
$i,j\in\{1,\ldots,n\}$, if $i$ precedes $j$ in the
list, then $x_i\le x_j$.
\end{itemize}
\noindent
Moreover, given slightly superlinear processor
and space bounds, these problems or variations
of them can be solved in
constant time with high probability.

As a corollary of the integer chain-sorting result,
it follows that $n$ integers in the range $1.. n$
can be sorted in $O({{\log n}/{\log\log n}})$ time
with optimal speedup with high probability.
Acknowledgement:
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-93-123.pdf49063 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: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1993-123 BibTeX
@TECHREPORT{BastHagerup93,
AUTHOR = {Bast, Holger and Hagerup, Torben},
TITLE = {Fast parallel space allocation, estimation and integer sorting (revised)},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-93-123},
MONTH = {June},
YEAR = {1993},
ISSN = {0946-011X},
}