How to sort faster than n log n (given a strong condition on the list)?
algorithm, c++, sorting
Solution
http://en.wikipedia.org/wiki/Radix_sort
the key fact is that you're working with integers and you know the largest key, which is exactly when radix sort is used and its complexity is linear.
also second approach if k of them are already sorted you can use some version of shell sort with sequence that will yield the best result
Problem
I was asked the following question (didn`t know at all the approach how to solve it) Given an array arr of n `int`s we need to sort it.We already know that k of this `int`s are placed in the original arr as in sorted array.(just don`t know which of them) They told that such sorting is much better than `nlogn` - i have no any clue... Any advices?