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.

  • $\begingroup$ +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. $\endgroup$
    – quicksort
    Jan 6 '17 at 21:31
  • $\begingroup$ @quicksort better to just sort the scraps and merge methinks $\endgroup$ Jan 6 '17 at 22:06
  • 1
    $\begingroup$ That's the same thing, but merging is cleaner, I agree. $\endgroup$
    – quicksort
    Jan 6 '17 at 22:09
  • 1
    $\begingroup$ Worthy of mentioning is that this is asymptotically optimal (using comparisons) in dependence on both n and k. $\endgroup$
    – aelguindy
    Jan 7 '17 at 2:00
  • $\begingroup$ Well, the algorithm you described seems to be drop-merge sort. $\endgroup$
    – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.