How might someone with (much) more knowledge explain this?

A common result in the analysis of sorting algorithms is that for n elements, the best average-case behavior of any sort algorithm—based solely on comparisons—is O(n log n).

How might a sort algorithm beat this average-case behavior based on additional prior knowledge of the data elements?

What sort of speed-up might be anticipated for such an algorithm? In other words, does it suddenly become O(n), O(n log n) or something similar?