TR-96-03: Randomized Sorting on Optically Interconnected Parallel Computer

In this paper we present an ecient randomized sorting algorithm for a multiprocessor computer which uses all-to-all broadcast freespace optical interconnects. This algorithm has a better time complexity compared to other sorting algorithms utilizing optical processing that have been proposed in the existing literature. The present algorithm has better performance compared to similar randomized sorting algorithms on electrically interconnected mutiprocessors, due to the higher bandwidths and parallelism of optical interconnections.