The Power of Collision: Randomized Parallel Algorithms for Chaining and Integer Sorting

We address the problem of sorting n integers each in the range {l, ... ,m}, for m = n to the O(l), in parallel on the PRAM model of computation. We present a randomized algorithm that runs with very high probability in O(log n/log log n) time with a processor-time product of O(n loglog m) and O(n) space on the CRCW (COLLISION) PRAM [13]. The improvements that this algorithm makes over existing ones [5, 20, 27] include a weakening of the model of computation used and reducing the space requirement to O(n), without increasing the time needed or work done. For larger values of m our algorithm is better than existing algorithms in several other ways as well. We show that the algorithm can be analyzed using O(log superscript O(l))-wise independence, which implies that the amount of true randomness needed is small. We also give an improved randomized algorithm for the problem of chaining [22,29]. An interesting subroutine used is an algorithm for solving a class of processor allocation problems quickly. The algorithms for chaining and integer sorting both make use of efficient algorithms for the construction of the fast priority queue of van Emde Boas [35]