One thing to note is that there are a lot of practical situations where we can get better than $O(n \log n)$ sorting. I'm not sure where the best reference is, but this library has a link to a video talk by Fritz Henglein, who is who I've heard originated the technique (unfortunately the links to his actual papers are broken).
The idea is to extend radix sort (or a similar sort, like flag sort) to much wider categories of values. In radix sort, we know in advance that we only need to do a fixed number of passes to sort the data, because our integers have a fixed size. This leads to $O(m \times n)$ performance, where $m$ is the necessary number of passes. For fixed sized integers, $m$ is a constant, so this is effectively $O(n)$.
It turns out that you can apply this methodology to pretty much any 'algebraic' type. For instance, if we have a type $A$ sortable in $i$ passes and $B$ in $j$ passes, then $A \times B$ can be sorted using $i + j$ passes, where the specifics will depend on which sort of radix sort you're using ($A$ first for top-down, $B$ first for bottom-up). And if we consider a type like:
data Either a b = L a | R b
then the most obvious way to handle this is via the top-down flag sort style, where we first distinguish based on
R and then proceed with $A$ and $B$, using $1 + \max(i,j)$ passes in general. So, any algebraic type with a finite maximum 'length' in this sense can be sorted in linear time (although the number of passes required may be large).
For recursive types (like strings), there is no fixed number of passes that are necessary, and in general it may require $\log n$ passes to fully distinguish $n$ values. (I'm not sure what a worst case example is. Probably something like sorting all prefixes of a given string.) However, particular examples might still run in sub-$(n \log n)$ time if they can be completely distinguished in fewer passes, and your algorithm is able to short-circuit the right way.