A general-purpose parallel sorting algorithm
and R. P. Brent,
A general-purpose parallel sorting algorithm,
International J. of High Speed Computing 7 (1995), 285-301.
Also the related Report:
R. P. Brent and
B. D. McKay,
Parallel integer sorting, Tech. Report, 13 Dec 1995, 32 pp.
Republished as Report TR-CS-97-10, CSL, ANU, May 1997.
A parallel sorting algorithm is presented for general purpose internal
sorting on MIMD machines. The algorithm initially sorts the elements
within each node using a serial sorting algorithm, then proceeds with
a two-phase parallel merge. The algorithm is comparison-based and
requires additional storage of order the square root of the number of
elements in each node. Performance of the algorithm on
the Fujitsu AP1000 MIMD supercomputer is discussed.
A preliminary version appeared as
For related work see
The Technical Report TR-CS-97-10 gives an extension to external sorting.
In the references, "Kolmos" should be "Komlós". Apologies to
János Komlós !
The parallel sorting code (parsort) is available from
Andrew Tridgell's website.
Go to next publication
Return to Richard Brent's index page