A Practical Algorithm for Integer Sorting on a Mesh-Connected Computer (Preliminary Version)

Abstract

This paper presents count-sort, a parallel algorithm for mesh- connected computers to sort integers where the range of inputs is known. A straightforward counting technique that has not been implemented previously in parallel sorting algorithms is presented. On a mesh-connected computer with square root N x square root N processors we are able to sort N integers in the range 1... square root N in time c square root N where c is very small. For practical values of N, the algorithm is extremely fast. Further, it is possible to expand the range by a factor k to 1 ... k square root N so that the slowdown is less than k. We produce an implementation of count-sort on the SIMD MasPar MP-1 with 8192 processors that sorts 8-bit integers significantly faster than the manufacturer's current library routine for sorting 8-bit integers.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 05, 1994
Accession Number
ADA283921

Entities

People

  • Ichiro Suzuki
  • Nathan Folwell
  • Sumanta Guha

Organizations

  • University of Wisconsin–Milwaukee

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Crossbar Switches
  • Language
  • Military Research
  • Parallel Computing
  • Parallel Processing
  • Permutations
  • Random Number Generators

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Linear Algebra
  • Parallel and Distributed Computing.