So, the only sort worth a damn in Quick Sort?

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!) .

▲

Fredkin 10 months ago | parent [-]

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

	▲	vrighter 10 months ago \| parent [-]
		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.