I&C Journal 1995 Journal Article
Fast Parallel Space Allocation, Estimation, and Integer Sorting
- H. Bast
- T. Hagerup
The following problems are shown to be solvable in O(log* n) time with optimal speedup with high probability on a randomized CRCW PRAM using O(n) space: • Space allocation: Given nonnegative integers, .. ., , allocate nonoverlapping blocks of consecutive memory cells of sizes, .. ., from a base segment of (∑) consecutive memory cells. • Estimation: Given integers in the range 1. ., compute "good" estimates of the number of occurrences of each value in the range 1. .. • Semisorting: Given integers, .. ., in the range 1. ., store the integers 1, .. ., in an array of () cells such that for all ∈ {1, .. ., }, all elements of {: 1 ≤ ≤ and = } occur together, separated only by empty cells. • Integer chain-sorting: Given integers, .. ., in the range 1. ., construct a linked list containing the integers 1, .. ., such that for all, ∈ {1, .. ., }, if precedes in the list, then ≤. 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.