Whats the best method to maintain or measure how well sorted a collection is so we can choose best sort algorithm?

Question

Inspired by this question

The choice of which algorithm to use to sort a collection can be made better if we know ahead of time how well sorted a collection is. Is there a way we can measure (or maintain a measurement) of how well sorted the collection is? Can we do this in such a way that the cost of maintaining or measuring how well sorted something doesn't outweigh the benefit of choosing the best sort algorithm?

Answer 1

Augmenting @Doug:

A deletion can never make the list less sorted, so you don't have to track those.

When an insertion happens, compare with the elements around to determine if this insertion was in-order or not. If yes, don't increase the counter. If no, increase the "not sorted" counter.

Perhaps this is too much of a penalty (i.e. two compares per insert). You could do only one compare for a more fuzzy result? Or I do like the idea of just counting inserts.