A Simple Optimal Randomized Parallel List Ranking Algorithm
ID
TR-87-14
Publishing date
May 1987
Abstract
We describe a randomized parallel algorithm to solve list ranking in $O(\log n)$ expected time using $n/ \log n$ processors, where $n$ is the length of the list. The algorithm requires considerably less load rebalancing than previous algorithms.
File(s)