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?