How to sort faster than n log n (given a strong condition on the list)?

Question

I was asked the following question (didn`t know at all the approach how to solve it) Given an array arr of n ints we need to sort it.We already know that k of this ints 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?

Answer 1

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