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

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.