Optimal Parallel Sorting on a Linear Processor Array

Abstract:

The problem of sorting n elements on k linearly connected processors is examined. We reduce the communication complexity (measured in units of single data transfers between adjacent processors) by a factor of two from the previous best bound while maintaining the same (asymptotically optimal) number
of comparisons. The result holds even if only unidirectional communication between processors is allowed (a unidirectional ring architecture). This result is significant because communication time dominates computation time in most realistic parallel sorting problems.