I wish it had a "pathological case" option for data to sort per-algorithm.
In particular: Quicksort, which (unless you're willing to make an (expensive) call to a (P)RNG per iteration) has a worst case of O(n^(2)) time.
In particular: Quicksort, which (unless you're willing to make an (expensive) call to a (P)RNG per iteration) has a worst case of O(n^(2)) time.
And merge sort is often faster, especially if the comparison function is relatively expensive.
"Engineering a Sort Function"[0] covers this quite well.
In some experiments of my own, I've found that even Smoothsort[1] (an algorithm specifically designed to have a smooth transition from linear to linearithmic behavior on nearly-sorted input) can't beat the C++ system's introsort (a quicksort variation with a fallback to heapsort) in already-sorted inputs.
[0] http://www.skidmore.edu/~meckmann/2009Spring/cs206/papers/sp...
Technically, the worst case stays the same.
In actuality, the worst case occurring via random chance is not a problem, as it occurs vanishingly infrequently. The problem is malicious input.