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).


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.


The Technical Report includes more details. For related work, see [142, 158].


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