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?