It is theoretically possible to sort an array in length(array) - length(longestIncreasingSubsequence(array)) moves by moving only elements that are not already in sorted order.

If the only operation allowed is an in place move, by removing an element from index A and reinserting it into index B, one element at a time, how would you generate the correct moves to end up with the sorted array? Again, there should be length(array) - length(longestIncreasingSubsequence(array)) moves required.

For example, here is an array:

[ 1, 8, 5, 2, 4, 6, 3, 9, 7, 10 ]

The longest increasing subsequence is:

[ 1, 2, 4, 6, 7, 10 ]

The indices of those elements are:

[ 0, 3, 4, 5, 8, 9 ]

So, the indices we need to move are:

[ 1, 2, 6, 7]

since those are the indices that are not already in sorted order.

In order to end up with a sorted array, the final indices of those 4 elements are:

[ 7, 4, 2, 8]

So, we need to simultaneously move index 1 to index 7, index 2 to index 4, index 6 to index 2, and index 7 to index 8. The problem is that when an element is moved, the other elements are shifted around making the later move operations invalid. I've tried transforming these indices, but so far have not come up with the correct list of moves required. Any ideas?

Hopefully I've explained the problem well enough. Please ask questions and I will clarify. Thanks!