Document Type
Article
Date
1997
Keywords
Integer sorting, Polynomially bounded elements, Distributed radix-sort algorithm, Digital arithmetic, Parallel machines
Language
English
Disciplines
Computer Sciences
Description/Abstract
Integer sorting is a subclass of the sorting problem where the elements have integer values and the largest element is polynomially bounded in the number of elements to be sorted. It is useful for applications in which the size of the maximum value of element to be sorted is bounded. In this paper, we present a new distributed radix-sort algorithm for integer sorting. The structure of our algorithm is similar to radix sort except that it typically requires less number of communication phases. We present experimental results for our algorithm on two distributed memory multiprocessors, the Intel Paragon and the Thinking machine CM-5. These results are compared with two other well known practical parallel sorting algorithms based on radix sort and sample sort. The experimental results show that the distributed radix-sort is competitive with the other two algorithms.
Recommended Citation
Alsabti, Khaled and Ranka, Sanjay, "Integer Sorting Algorithms for Coarse-Grained Parallel Machines" (1997). College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects. 44.
https://surface.syr.edu/lcsmith_other/44
