Parallel iterated bucket sort (Q1263965)

We develop a parallel algorithm sorting n integers, drawn randomly from a polynomial range, on a CRCW PRAM using n/log n processors in time O(log n) with probability \(1-2^{-bn/\log^ 3n}\), for some \(b>0\). The algorithm, called iterated bucket sort, is an improvement over an algorithm given by Chlebus, where the input integer keys were restricted to be of linear magnitude. Recently a similar result has been announced by Hagerup.