We consider the problem of sorting n integers in the range [O, n(c)- I
], where c is a constant. It has been shown by Rajasekaran and Sen [14
] that this problem can be solved ''optimally'' in O(log n) steps on a
n EREW PRAM with O(n) n(epsilon)-bit operations, for any constant epsi
lon > 0. Though the number of operations is optimal, each operation is
very large. In this paper, we show that n integers in the range [0, n
(c) - 1] can be sorted in O(log n) time with O(n log n) O(1)-bit opera
tions and O(n) O(log n)-bit operations. The model used is a non-standa
rd variant of an EREW PRAM that permits processors to have word-sizes
of Theta(1)-bits and O(log n)bits. Clearly, the speed of the proposed
algorithm is optimal. Considering that the input to the problem consis
ts of O(nlog n) bits, the proposed algorithm performs an optimal amoun
t of work, measured at the bit level.