PARALLEL INTEGER SORTING USING SMALL OPERATIONS

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.