DA-Sort

This problem asks us how many insertions does it take to do an insertion sort. One can come up with a pessimal solution by inserting the numbers in order for n inserts. But we quickly realize

• we never would have to insert the smallest number...since it will end up in the right place if we insert all the rest of the numbers after it!
• we don't have to insert the next number if it's already to the right of the smallest number
• we don't have to insert the next number if it's already to the right of the next smallest number.
• etc.

This leads to a trivial rule of "we have to insert every number after and including the first number which appears out of order.

We have to deal with the fact, though, that we can have repeats and integers may not be consecutive. This is relatively straightforward. We can start by mapping the unique values in the list to consecutive integers (all the smallest value gets 1, the next smallest set of values become 2, etc).

To deal with the multiples, the same rule above applies. but for any set of a given number which is DIVIDED across the LAST of the next smallest number, we only have to insert those of which occur BEFORE the last of that number. So if we have

1112112212222

We have to perform 3 insertions because 3 2's appear BEFORE the last one. In such a case, we would also have to perform insertions for every number greater than 2.