OPTIMAL PARALLEL ALGORITHM FOR INTEGER SORTING.

Published

Journal Article

A new parallel algorithm is given for integer sorting where the integer keys are restricted to at most polynomial magnitude. The algorithm costs only logarithmic time and is the first known where the product of the time and processor bounds are bounded by a linear function of the input size. These simultaneous resource bounds are asymptotically optimal. All previous known parallel sorting algorithms required at least a linear number of processors to achieve logarithmic time bounds and hence were nonoptimal by at least a logarithmic factor.

Duke Authors

Cited Authors

  • Reif, JH

Published Date

  • December 1, 1985

Published In

Start / End Page

  • 496 - 504

International Standard Serial Number (ISSN)

  • 0272-5428

Citation Source

  • Scopus