Improved nonconservative sequential and parallel integer sorting

Torben Hagerup, Hong Shen

Research output: Contribution to journalArticlepeer-review

18 Citations (Scopus)


We consider the problem of deterministic integer sorting on unit-cost sequential and parallel machines with a large word length and show that n integers drawn from {0,...,m-1} can be sorted using a word length of O(m log n) bits either in O(n) time on a unit-cost RAM or in O(log n) time on a unit-cost EREW PRAM with O(n/log n) processors. Spending O(log log log m) additional sequential or parallel time, we can reduce the necessary word length to O(min}n log n log m + (log m)1+ε{lunate}, mε{lunate}+log n}) bits, for any fixed ε{lunate}>0. Previous algorithms with a linear time-processor count either cannot so arbitrary integers or require a much larger word length.

Original languageEnglish
Pages (from-to)57-63
Number of pages7
JournalInformation Processing Letters
Issue number2
Publication statusPublished - 15 Oct 1990
Externally publishedYes


  • Integer sorting
  • nonconservative algorithms
  • parallel algorithms
  • parallel sorting
  • unit-cost measure
  • word length


Dive into the research topics of 'Improved nonconservative sequential and parallel integer sorting'. Together they form a unique fingerprint.

Cite this