Fast parallel space allocation, estimation and integer sorting (revised)
Holger Bast, Torben Hagerup · Max Planck Digital Library · 1993
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} \ oindent 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.