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?

  • $\begingroup$ Presumably, you mean $n^{2/3}$ (which is a minority of elements). You can combine two types of sorts depending on whether the elements are in the given range or not. $\endgroup$
    – user16034
    Commented Feb 14, 2023 at 9:19
  • $\begingroup$ This can work with any exponent less than one. $\endgroup$
    – user16034
    Commented Feb 14, 2023 at 9:26

1 Answer 1


The reason you are provided that information is that, without this extra promise, it is not possible to sort in linear time. With this extra promise, it is possible to sort in linear time.

It's your exercise, so I will leave it to you to come up with the strategy to sort such an array in linear time. Once you've found such an algorithm, hopefully you will be able to see why the same can't be used on any array (without that promise).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.