Parallel integer sorting using small operations

Ramachandran Vaidyanathan, Carlos R.P. Hartmann, Pramod K. Varshney

Research output: Contribution to journalArticle

4 Scopus citations

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 languageEnglish (US)
Pages (from-to)79-92
Number of pages14
JournalActa Informatica
Volume32
Issue number1
DOIs
StatePublished - Jan 1 1995

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Parallel integer sorting using small operations'. Together they form a unique fingerprint.

  • Cite this