[brmgb]

The bound is a bound on comparaison sort not a general bound on sorting.

If you don't use comparaison you can sort faster. Pigeonhole sort is linear for example.

[MaxBarraclough]

Right, comparative and non-comparative sorting algorithms.

I'd say radix sort is the canonical example of a non-comparative sorting algorithm.