<p>Inspired by <a href="https://stackoverflow.com/questions/220044/which-sort-algorithm-works-best-on-mostly-sorted-data">this question</a></p>

<p>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?</p>

You could use sampling: Check N elements spaced evenly in the list and see how many are in order.  (Of course that only works in a random-access list, but usually that's the type you sort.)
Also have a threshold for small N.  If N is small (e.g.
```
10
```
) insertion sort is good even if the list isn't sorted.  Java makes this optimization for small N in what is otherwise a merge-sort.