Sorting an "almost sorted" array in sub linear time

Question

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?

Answer 1

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.

Answer 2

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!