A fast, storage-efficient parallel sorting algorithm
140. R. P. Brent and
A. Tridgell,
A fast, storage-efficient parallel sorting algorithm,
Proceedings of the International Conference on
Application-Specific Array Processors held at Venice, Italy, Oct. 1993
(edited by L. Dadda and B. Wah), IEEE CS Press,
1993, 369-379.
Also
An implementation of a general-purpose parallel sorting algorithm,
Report TR-CS-93-01, CSL, ANU, February 1993, 24 pp.
Abstract:
dvi (3K),
pdf (31K),
ps (28K).
Paper:
dvi (24K),
pdf (87K),
ps (48K).
Report:
dvi (41K),
pdf (110K),
ps (90K).
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, Thinking Machines CM5, and nCUBE2 is discussed.
The performance is good: efficiencies of 0.8 to 0.9 are typical when
sorting a large number of elements.
Comments
The Technical Report includes more details.
For related work, see
[142,
158].
Erratum
In the references, "Kolmos" should be "Komlós"
and "Szermeredi" should be "Szemerédi".
Apologies to
János Komlós
and
Endre Szermerédi!
Go to next publication
Return to Richard Brent's index page