[contravariant]

What makes things tricky is that there are a couple of common cases that can be sorted in O(n), and that more complicated algorithms might have better asmyptotic behaviour, while being worse for small or even moderately large lists.

To make matters worse there are also more specific sorting algorithms like radix sort, which can be even faster in cases where they can be used.