[Fredkin]

The radix msd sort seems to do well on valley and mountain.

[vrighter]

But radix sort is its own beast (a variant of counting sort).

It requires O(N) memory, but since it is not a comparison sort, it also sorts in O(N). But it can only sort integers. So not exactly an apples-to-apples comparison.