# A Simple Optimal Randomized Parallel List Ranking Algorithm

ID
TR-87-14
Authors
Karl Abrahamson, Norm Dadoun, David G. Kirkpatrick and Teresa Maria Przytycka
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.