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