Proof for time complexity of Insertion (k-proximate) Sort equals O(nk) The following is the definition for Proximate Sorting given in my paper:
An array of distinct integers is k-proximate if every integer of the array is at most k places away
from its place in the array after being sorted, i.e., if the $i$th integer of the unsorted input array is the
$j$th largest integer contained in the array, then $|i − j| ≤ k$.
The following is the proof for time complexity of k-proximate insertion sort:
To prove $O(nk)$, we show that each of the n insertion sort rounds swap an
item left by at most $O(k)$.
In the original ordering, entries that are $≥ 2k$ slots apart must already be ordered
correctly: indeed, if $A[s] &gt; A[t]$ but $t − s ≥ 2k$, there is no way to reverse the
order of these two items while moving each at most $k$ slots. This means that for
each entry $A[i]$ in the original order, fewer than $2k$ of the items $A[0], . . . , A[i−1]$
are less than $A[i]$. Thus, on round $i$ of insertion sort when $A[i]$ is swapped into
place, fewer than $2k$ swaps are required, so round $i$ requires $O(k)$ time.
My problem with the proof is this line : &quot;This means that for each entry A[i] in the original order, fewer than 2k of the items $A[0], . . . , A[i−1]$ are less than A[i]&quot;. The preceding statements just proved that $t-s &lt; 2k$, otherwise the elements are sorted (as elements with distance greater than $2k$ cannot be swapped.) Isn't the correct statement : &quot;This means that for each entry A[i] in the original order, fewer than 2k of the items $A[0], . . . , A[i−1]$ are greater than A[i]&quot;?
Yes if you sort the array in ascending order you are right it should be less than $2k$ elements in $A[0],...,A[i-1]$ are greater than $A[i]$. A simple array were the statement w is wrong  ($k = 1$):
$$[1,2,3,4]$$
However is you sort in descending order it's the other way around.
But you have a good point because this seems to imply that ascending is meant...

&quot;indeed, if A[s] &gt; A[t] but t − s ≥ 2k, there is no way to reverse the order of these two items&quot;