Let A[1 : n] be a vector of n integers such that all elements except O(n^2/3) elements are between 1 and 10n. Design an algorithm with linear complexity that sorts A.
Beyond the algorithm, what I can't fully understand is why we are provided with the information "all elements except O(n^2/3)" It is certainly an information that guides the choice in some way of the algorithm. What considerations can we make on this information that is provided to us?. How can it guide us in choosing the best algorithm?