I have an n-element array. All elements except
4√n of them are sorted. We do not know the positions of these misplaced elements. What is the most efficient way of sorting this list?
Is there an O(n) way to do this?
time complexity of an insertion sort is O(n) for almost sorted data (is it true in worst case?)?