A GENERAL-PURPOSE PARALLEL SORTING ALGORITHM

Authors
TRIDGELL A BRENT RP
Citation
A. Tridgell et Rp. Brent, A GENERAL-PURPOSE PARALLEL SORTING ALGORITHM, International journal of high speed computing, 7(2), 1995, pp. 285-301
Citations number
18
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
International journal of high speed computing → ACNP
ISSN journal
01290533
Volume
7
Issue
2
Year of publication
1995
Pages
285 - 301
Database
ISI
SICI code
0129-0533(1995)7:2<285:AGPSA>2.0.ZU;2-J
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 requ ires additional storage of order the square root of the number of elem ents in each node. Performance of the algorithm on the Fujitsu AP1000 MIMD supercomputer is discussed.