ANU Computer Science Technical Reports
Andrew Tridgell, Richard Brent, and Brendan McKay.
Parallel integer sorting.
The work documented in this report was completed in December 1995.
[POSTSCRIPT (142687 bytes)]
Abstract: This paper presents algorithms and
experiments for internal (in core) and external (secondary memory) parallel
sorting. It concentrates on algorithms appropriate for medium scale MIMD
parallel computers, with all experiments being performed on a 128 processor
Data sizes ranging from a few hundred thousand to a
few hundred million elements are considered, with all elements being either
64 bit or 128 bit integers.
The internal sorting algorithm is based on
earlier work by Andrew Tridgell and Richard Brent [TR-CS-93-01], while the
external sorting algorithm was developed for this paper.
also takes a quick look at serial sorting algorithms, as they play an
important part as subroutines in the parallel sorting algorithms.
Technical Reports <Technical.Reports@cs.anu.edu.au>
Last modified: Mon May 26 14:17:28 EST 1997