Improved Sorting Algorithms for Parallel Computers
Abstract:
We make observations that improve processor utilization and decrease communication overhead for several parallel sorting algorithms. These lead to constant factor improvements on the best previous parallel sorting bounds for both mesh-connected and linearly connected parallel architectures. (Previous
bounds were within a constant factor of optimal.) These improved bounds are achieved using fewer processors with greater processor utilization.