Not necessarily. Initialize the data to "Mountain" or "Valley" and run quicksort, and you get O(n^2) behaviour.

Quicksort is best for randomized data. In fact, the best way to guarantee good performance from quicksort is to shuffle the data first! Well, it is theoretically possible that shuffling might yield a valley or other unlucky input, but the odds of that are O(1/n!) .

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