## Abstract

We consider the problem of sorting n integers in the range [0, n^{c}-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, n^{c}-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 1 1995 |

## ASJC Scopus subject areas

- Software
- Information Systems
- Computer Networks and Communications