Comparison of Sorting Algorithms for the Connection Machine CM-2

摘要

The authors evaluate the implementation of three parallel sorting algorithms on the Connection Machine Supercomputer model CM-2. The three selected were Batcher's bitonic sort, a parallel radix sort, and a sample sort similar to Reif and Valiant's flashsort. The paper analyzes the three algorithms in detail. Although the programs were designed for the CM-2, the conclusions about the merits of the three algorithms apply to other parallel machines as well. The experiments show that the sample sort is the fastest of the three algorithms for large data sets. Radix sort, although not as fast for large data sets, is deterministic, much simpler to code, stable, faster with small keys, and faster on small data sets (few elements per processor). Bitonic sort is the least efficient of the three on large data sets, but is the most efficient on small data sets and is considerably more space efficient.