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 you anticipate for such an algorithm? In other words, does it suddenly become O(n), O(n log n) or something similar?