## Abstract

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 language | English |
---|---|

Pages (from-to) | 57-63 |

Number of pages | 7 |

Journal | Information Processing Letters |

Volume | 36 |

Issue number | 2 |

DOIs | |

Publication status | Published - 15 Oct 1990 |

Externally published | Yes |

## Keywords

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