A simple optimal list ranking algorithm

We consider the problem of ranking an N element fist on a P processor EREW PRAM. Recent work on this problem has shown the importance of grain size. While several optimal O(N/P + log P) time fist ranking algorithms are known, Reid-Miller and Blelloch recently showed that these do not lend to good implementations in practice[6, 7], because of the fine-grained nature of these algorithms. In Reid-Miller and Blelloch's experiments the best performance was obtained by an O(N/P + log(2) P) time coarse grained randomized algorithm devised by them. I;Ve build upon their idea ann present a coarse-grained randomized algorithm that runs in time O(N/P +/- log P), mid is thus also optimal. Our algorithm simplifies some of the ideas from [6, 7] - these simplifications might be of interest to implementors