## 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