  We investigate distributed memory parallel sorting algorithms that scale to
the largest available machines and are robust with respect to input size and
distribution of the input elements. The main outcome is that four sorting
algorithms cover the entire range of possible input sizes. For three algorithms
we devise new low overhead mechanisms to make them robust with respect to
duplicate keys and skewed input distributions. One of these, designed for
medium sized inputs, is a new variant of quicksort with fast high-quality pivot
selection.
  At the same time asymptotic analysis provides performance guarantees and
guides the selection and configuration of the algorithms. We validate these
hypotheses using extensive experiments on 7 algorithms, 10 input distributions,
up to 262144 cores, and varying input sizes over 9 orders of magnitude. For
difficult input distributions, our algorithms are the only ones that work at
all. For all but the largest input sizes, we are the first to perform
experiments on such large machines at all and our algorithms significantly
outperform the ones one would conventionally have considered.
