Load balanced sort on hypercube multiprocessors

Abstract

A parallel algorithm for sorting n elements evenly distributed over 2d = p nodes of a d dimensional hypercube is given. The algorithm ensures that the nodes always receive equal number of elements (n/p) at the end, regardless of the skew in data distribution.