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


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 [140]. For related work see [142]. 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