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] > 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, . . . , 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 : "This means that for each entry A[i] in the original order, fewer than 2k of the items $A, . . . , A[i−1]$ are less than A[i]". The preceding statements just proved that $t-s < 2k$, otherwise the elements are sorted (as elements with distance greater than $2k$ cannot be swapped.) Isn't the correct statement : "This means that for each entry A[i] in the original order, fewer than 2k of the items $A, . . . , A[i−1]$ are greater than A[i]"?