Practical sorting algorithms for hypercube computers.
Bruce Alan Wagar · Deep Blue (University of Michigan) · 1990
We consider the problem of designing a practical and efficient sorting algorithm for hypercube computers. The advent of commercial hypercube machines in the past several years has sparked much interest in this problem. We came up with one of the first such algorithms, hyperquicksort. Its description and implementation are very straightforward. Still other algorithms were devised, either concurrently with or later than hyperquicksort. Substantial amounts of empirical analysis have been carried out on their behavior. We summarize these results and show how hyperquicksort has outperformed the other, often more sophisticated, algorithms. Extensive empirical results--obtained from a custom software simulation package--as well as some rigorous theoretical analysis are provided to back up our claims. In addition, we present possible enhancements to hyperquicksort to improve its performance in special situations. Finally, we explain modifications to the basic algorithm that allow it to run on other parallel machines, not just hypercubes.