Probabilistic integer sorting

Alexandros V. Gerbessiotis, Constantinos J. Siniolakis

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

We introduce a probabilistic sequential algorithm for stable sorting n uniformly distributed keys in an arbitrary range. The algorithm runs in linear time and sorts all but a very small fraction 2-Ω(n) of the input sequences; the best previously known bound was 2 -Ω(n/(lgnlglgn)). An EREW PRAM extension of this sequential algorithm sorts in O((n/p+lgp)lgn/lg(n/p+lgn)) time using p≤n processors under the same probabilistic conditions. For a CRCW PRAM we improve upon the probabilistic bound of 2-Ω(n/(lgnlglgn)) obtained by Rajasekaran and Sen to derive a 2-Ω(nlglgn/lgn) bound. Additionally, we present experimental results for the sequential algorithm that establish the practicality of our method.

Original languageEnglish (US)
Pages (from-to)187-193
Number of pages7
JournalInformation Processing Letters
Volume90
Issue number4
DOIs
StatePublished - May 31 2004

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Keywords

  • Analysis of algorithms
  • Integer sorting
  • Sorting uniform keys

Fingerprint Dive into the research topics of 'Probabilistic integer sorting'. Together they form a unique fingerprint.

Cite this