# Sorting an "almost sorted" array in sub linear time

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.

• 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.
– AmirB
Dec 22, 2015 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!

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