I am given an "almost sorted" array with the condition that each element is no more than $k$ places away from its position in the sorted array. I need to show that it is impossible to sort this array in sublinear time asymptotically.

My proof is to suppose a sorted array of length $n$. Now assume that every second element is swapped with the element on its left. The new array is almost sorted. To sort it would require a minimum of $n/2$ swaps - asymptotically linear amount of operations. Therefore, no sublinear sorting algorithm exists.

Is this proof correct?


It is correct, but you should be careful to stipulate that the swaps are performed in a non overlapping fashion; if the swaps overlap then one element can be carried across the array breaking the guarantee.

  • $\begingroup$ Thank you, perhaps i did not explain well but the swaps can not overlap as i swap two adjecent elements: element one with two, three with four, and so on. $\endgroup$ – AmirB Dec 22 '15 at 8:21

This is correct, but more complicated than it needs to be.

Consider an array of $n$ elements which is sorted except for that one (unknown) pair of elements is swapped.

Since the sorting algorithm does not know in which pair of elements is swapped, any individual element of the array may be in the wrong place. So, we have to make $O(n)$ comparisons to check if each element needs to be moved or not.

Therefore, the complete algorithm cannot be faster than $O(n)$.

The condition that "each element is no more than $k$ places away from its position" is irrelevant, though it might mislead you to waste time looking for a faster algorithm which depends on that condition!

  • $\begingroup$ But this is actually not trivial to formally prove -- I think the original one may be just as easy. $\endgroup$ – usul Mar 25 at 17:13

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.