- An experimental analysis of parallel sorting algorithms
. G. E. Blelloch, C. E. Leiserson, B. M. Maggs, C.
G. Plaxton, S. Smith, and M. Zagha, Theory of Computing Systems,
Vol. 31, No. 2, March/April 1998, pp. 135-167.
- This paper describes a project whose mission was to improve the
performance of the system sorting software for the Connection Machine
model CM-2. We implemented three parallel sorting algorithms:
Batcher's bitonic sort, a parallel radix sort, and a sample sort
similar to Reif and Valiant's flashsort. We also evaluated the
implementation of many other sorting algorithms proposed in the
literature. Our experiments showed that the sample sort algorithm is
the fastest of the three on large data sets. The radix sort, although
not as fast on large data sets, is simpler to code, stable, and faster
with small keys or small data sets. Bitonic sort is the fastest of
the three for small data sets and also the most space efficient. This
paper discusses the implementation and performance of the three
algorithms, and the issues that led us to choose them over other
algorithms in the literature.
- Back to other
- Back to my home page