We consider the problem of sorting n integers in the range [0, nc-1], where c is a constant. It has been shown by Rajasekaran and Sen  that this problem can be solved "optimally" in O(log n) steps on an EREW PRAM with O(n) n∈-bit operations, for any constant ∈>O. Though the number of operations is optimal, each operation is very large. In this paper, we show that n integers in the range [0, nc-1] can be sorted in O(log n) time with O(nlog n)O(1)-bit operations and O(n) O(log n)-bit operations. The model used is a non-standard variant of an EREW PRAMtthat permits processors to have word-sizes of O(1)-bits and Θ(log n)-bits. Clearly, the speed of the proposed algorithm is optimal. Considering that the input to the problem consists of O (n log n) bits, the proposed algorithm performs an optimal amount of work, measured at the bit level.
ASJC Scopus subject areas
- Information Systems
- Computer Networks and Communications