A general-purpose parallel sorting algorithm
158.
A. Tridgell
and R. P. Brent,
A general-purpose parallel sorting algorithm,
International J. of High Speed Computing 7 (1995), 285-301.
Abstract:
dvi (3K),
pdf (65K),
ps (27K).
Paper:
dvi (43K),
pdf (226K),
ps (80K).
Also the related Report:
A. Tridgell,
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.
Report:
pdf (318K),
ps (141K).
Abstract
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.
Comments
A preliminary version appeared as
[140].
For related work see
[142].
The Technical Report TR-CS-97-10 gives an extension to external sorting.
Erratum
In the references, "Kolmos" should be "Komlós". Apologies to
János Komlós !
Software
The parallel sorting code (parsort) is available from
Andrew Tridgell's website.
Go to next publication
Return to Richard Brent's index page