I came across a problem in stackoverflow. The problem gives you an array and a value 'K'. You can move an element to right at any position, but you can't move it more than K positions left. Find the optimal ordering on which number of inversions is minimum, e.g. array 3,2,1 has 3inversions. For K=1, solution array is: 2,1,3.

I had a greedy algorithm for this problem, but can't prove its correctness (though I'm pretty sure about its correctness):

iterate the array from left to right.
For each position i we consider a subarray from i to i+k. Then we find the minimum valued element on this subarray and insert this element at the beginning of the subarray and right shift the elements between this interval.
Now, go to position i+1 and do the same.

for example:

given array = 5 3 4 7 8 2 1 0 and K = 2

This algorithm gets the solution array as this:

3 4 5 2 1 0 7 8
minimum inversion value = 12

This is just a naive version of algorithm which we can make as fast as O(nlogn).

How would you prove it if this algorithm is right?

Help is greatly appreciated.