Histogram Sort with Sampling

To minimize data movement, state-of-the-art parallel sorting algorithms use sampling and histogramming techniques to partition keys prior to redistribution. Samples enable partitioning to be done using representative subset of the keys, while histogramming enables evaluation and iterative improvement of a given partitioning. We introduce Histogram sort with sampling (HSS), which combines sampling and histogramming techniques to find high-quality partitions with minimal data movement and high practical performance. Compared to the best known algorithm for finding this partitioning, our algorithm requires a factor of {\Theta}(log(p)/ log log(p)) less communication than the best known (recently introduced) alternative, and substantially less when compared to standard variants of Sample sort and Histogram sort. We provide a distributed-memory implementation of the proposed algorithm and compare its performance to two existing implementations, and provide a brief application study showing the benefit of the new algorithm.