I'm trying to understand how can I sort an array of $n$ elements when only $\log n$ are not in place.
I heard that sorting an array with at most $I$ inversions has complexity $O(n\log(I/n))$. Because there are $\log n$ elements that are unsorted, in my case there are at most $n\log n$ inversion.
The answer to the question is $O(n\log\log n)$ which is consistent with the formula, but I can't understand the"idea behind it, or which sorting algorithm achieves it.
Assuming that "$k$ elements out of place" means that there exist $k$ elements whose deletion leaves the rest of the array sorted, there's an $O(n+k\log k)$-time algorithm to sort the whole array.
In a nutshell, compute an increasing subsequence of length at least $n-2k$, sort the others, and merge. The former can be accomplished in time $O(n)$ by a simple stack algorithm that pushes elements one at a time and pops the top two whenever they're out of order. The optimal deletion strategy must delete at least one of these elements, so the total damage is upperbounded by $2k$ deletions.
Let's say there are $k$ non-in place elements.
Split the array into non-decreasing subarrays. This can be done in $\Theta(n)$ time and will result in at most $2k$ subarrays. Now we just pairwise-merge them in $\Theta(n \log k) $ time, yielding a sorted array.
