# 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 ith integer of the unsorted input array is the jth largest integer contained in the array, then |i − j| ≤ k. In this problem, we will show how to sort a k-proximate array faster than Θ(n log n).

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[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 : "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]". 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[0], . . . , A[i−1] are greater than A[i]"?