MPI-I-93-123

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.