OPTIMAL PARALLEL INTEGER SORTING ON EREW PRAM

摘要

Sorting is one of the most important algorithmic problems used as a subroutine in many applications such as database, pattern recognition and computational geometry. We present a new simple deterministic optimal parallel algorithm based on sell-index sort for sorting n integers in the range {l,...,n} in time O(log n) using n/log n processors on EREW PRAM. Our algorithm is optimal and belongs to ENC.