Abstract
We consider the problem of sorting n integers when the elements are drawn from the restricted domain [1...n]. A new deterministic parallel algorithm for sorting n integers is obtained. Its running time is O(log n log(n/log n)) using n/log n processors on EREW (exclusive read exclusive write) PRAM (parallel random access machine). Also, our algorithm was modified to become optimal when we use rootn processors. This algorithm belongs to class EP (Efficient, Polynomial fast).