Search

The author presents a practical sorting algorithm for a nearest-neighbor connected array of MIMD (multiple-instruction, multiple-data-stream) processors, each handling a significant fraction of the elements to be sorted. The algorithm is communication and CPU-optimal for a linear array, is almost order-preserving, and requires little working memory. >

The authors have designed a hybrid sorting algorithm using heapsort and a modified version of quicksort. It consists of two phases: preprocessing and sorting. In the preprocessing phase, input data are randomly placed on a square grid and sorted in column-wise order followed by row-wise order using heapsort. In the sorting phase, the preprocessed data are treated as a linear list and sorted by a modified quicksort. The sort time complexity of the hybrid method is O(n log/sub 2/n), and maintains a fairly constant value for a fixed n for any presortedness of the input data. The granularity of parallelism in the hybidsort is large, and therefore it is suitable for parallel processing. >