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