We consider the problem of sorting n numbers that contain only k disti
nct values. We present a randomized arbitrary CRCW PRAM algorithm that
runs in O(log n) time using (n log k)/log n processors. The same algo
rithm runs in O((log n)/log log n) time with a total work of O(n (log
k)(1+epsilon)) for any fixed epsilon > 0. All the stated bounds hold w
ith high probability. (C) 1998 Published by Elsevier Science B.V. All
rights reserved.