Abstract

Many sorting algorithms that perform well on uniformly distributed data suffer significant performance degradation on non-random data. Unfortunately many real-world applications require sorting on data that is not uniformly distributed. In this thesis, we propose a new strategy, A-ranksort, for sorting on parallel machines which has a stable behavior on input distributions of different entropies. Our sorting algorithm essentially consists of deterministically computing approximate ranks for the input keys, and using these to route to destinations that are guaranteed to be close to the final destination, and finally using a few steps of odd-even transposition sort to complete the sorting. We implemented A-ranksort, B-flashsort (40), Radix sort (20), and Bitonic sort (6) on a 2048 processor Maspar MP-1. Thearling (73) proposes a test suite of inputs with which to evaluate the performance of sorting algorithms. We tested all the algorithms on a very similar test suite. Using similar ideas, we also designed a new deterministic selection algorithm for integers that is simple and fast. (Abstract shortened by UMI.)