Abstract
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 [14] 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.
Original language | English (US) |
---|---|
Pages (from-to) | 79-92 |
Number of pages | 14 |
Journal | Acta Informatica |
Volume | 32 |
Issue number | 1 |
DOIs | |
State | Published - Jan 1995 |
ASJC Scopus subject areas
- Software
- Information Systems
- Computer Networks and Communications