MPI-INF/SWS Research Reports 1991-2021

# MPI-I-93-123

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

### Bast, Holger and Hagerup, Torben

#### June 1993, 85 pages.

.
##### Status: available - back from printing

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.

URL to this document: https://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},
}