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.