Towards optimal parallel radix sorting

R. Vaidyanathan, C. R.P. Hartmann, P. K. Varshney

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

The authors propose a radix sorting algorithm for n m-bit numbers (where m= Omega (log n) and polynomially upper bounded in n) that runs in O(t(n)log m) time, on any PRAM with mp(n)/logn logm O(logn)-bit processors; p(n) and t(n) are the number of processors and time needed for any deterministic algorithm to sort n logn-bit numbers stably (integer sorting) on the same type of PRAM as used by the radix sorting algorithm. The proposed algorithm has the same factor of inefficiency (if any) as that of the integer sorting algorithm used by it.

Original languageEnglish (US)
Title of host publicationProceedings of 7th International Parallel Processing Symposium, IPPS 1993
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages193-197
Number of pages5
ISBN (Electronic)0818634421, 9780818634420
DOIs
StatePublished - Jan 1 1993
Externally publishedYes
Event7th International Parallel Processing Symposium, IPPS 1993 - Newport, United States
Duration: Apr 13 1993Apr 16 1993

Publication series

NameProceedings of 7th International Parallel Processing Symposium, IPPS 1993

Conference

Conference7th International Parallel Processing Symposium, IPPS 1993
CountryUnited States
CityNewport
Period4/13/934/16/93

ASJC Scopus subject areas

  • Computer Science Applications
  • Hardware and Architecture
  • Software
  • Computational Theory and Mathematics
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Towards optimal parallel radix sorting'. Together they form a unique fingerprint.

  • Cite this

    Vaidyanathan, R., Hartmann, C. R. P., & Varshney, P. K. (1993). Towards optimal parallel radix sorting. In Proceedings of 7th International Parallel Processing Symposium, IPPS 1993 (pp. 193-197). [262880] (Proceedings of 7th International Parallel Processing Symposium, IPPS 1993). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/IPPS.1993.262880