Sort an array of $n$ elements when only $\log n$ are not in place

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.

StackExchange Computer Science Q#68329, answer score: 9