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.

• +1 for the neat idea. Just one thing (and I'm probably splitting hairs here), can you really make insertions in arbitrary places avoiding the $O(n)$ "everyone shift right please" cost? I believe we should keep track of the insertions in a separate structure, making one final pass at the end to produce the sorted array. – quicksort Jan 6 '17 at 21:31
• @quicksort better to just sort the scraps and merge methinks – David Eisenstat Jan 6 '17 at 22:06
• That's the same thing, but merging is cleaner, I agree. – quicksort Jan 6 '17 at 22:09
• Worthy of mentioning is that this is asymptotically optimal (using comparisons) in dependence on both n and k. – aelguindy Jan 7 '17 at 2:00
• Well, the algorithm you described seems to be drop-merge sort. – Morwenn Jan 17 '17 at 22:36

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.