Sort an array of $n$ elements when only $\log n$ are not in place
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.