Optimal Round and Sample-Size Complexity for Partitioning in Parallel Sorting

Wentao Yang, Vipul Harsh, Edgar Solomonik

State-of-the-art parallel sorting algorithms for distributed-memory architectures are based on computing a balanced partitioning via sampling and histogramming. By finding samples…