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

  Postscript Compressed Postscript
  Back to other publications

  Back to my home page