Limited sort: is this a well-known problem? I came up with a problem, and I'm having trouble finding existing work on it. I'm not sure if there is a polynomial-time solution for it. Is this a well-known problem (or equivalent to one)?

We define a function limited_sort(input, n) -&gt; output that takes an array of comparable elements input and an integer n and returns output which is a permutation of input such that that no element in output is more than n spaces from its original position in input. output is the permutation that has the lowest number of inversions (subsequent elements a, b such that a &gt; b) out of all such permutations (if there are multiple minimal permutations, output is the lexicographically lowest of them).

For example, limited_sort([4, 1, 0, 2, 3], 2) returns [0, 1, 4, 2, 3], which has 1 inversion (4, 2). 0 inversions is not possible because you'd have to fully sort the list, and the element "4" would move 4 spaces which is not allowed. [4, 0, 1, 2, 3] is also valid with 1 inversion but it's lexicographically higher than [0, 1, 4, 2, 3].

Is there a solution that is polynomial-time in both n and L (the length of input)?
I think absolutely minimising the number of inversions makes this very hard. If you just say "I want an array that is a bit better sorted, without moving any item by more than n positions": Fill a heap with the first n+1 array elements. Then remove the smallest element in the heap and put it into the first array position, unless there is an array element in the heap that would end up moving too far. Add the next array element to the heap and repeat. Obviously stop adding elements to the heap when you run out of elements. 

This will find [0, 1, 4, 2, 3] in your example.