Doing some research on this it appears to be untrue.

The limit on time complexity is for sorts based on comparisons (thought in the sort time I have been looking into this I have not seen a proof). It turns out that there are faster sorts (bucket sort for one) which have under certain conditions on the input data have an expected time complexity of

RonL