A sequence of distinct numbers A is going to be sorted using insertion sort. Insertion sort works as follows:
insertionsort(A)
initialize a new empty sequence R
for each number N in A (in the original order) do:
determine the index i in R where N should be inserted so that R remains sorted
move each element in R with index greater than or equal to i to the following index
set R[i]=N
return R
For example, an insertion sort on {20,40,30,10} would produce the following states for R after each step:
20 (first element is inserted at index 0)
20,40 (inserting 40 at index 1 requires no moves)
20,30,40 (30 is inserted at index 1, so 40 has to be moved)
10,20,30,40 (10 is inserted at index 0, so 20, 30 and 40 have to be moved)
In total, 4 moves were needed.
Given a int[] A, which contains a sequence of distinct numbers, return the number of moves that would be performed by an insertion sort on A.
