It's not uncommon to have data that is almost sorted, or some data that is sorted and some data that is not sorted. For example, I was just working with a function that had one unsorted element, either at the beginning or end of an array, that needed to be sorted.

It might be nice to provide some guidance to users about the performance in this case; would Go still issue around n*log(n) calls to sort the data, or would the actual number be closer to n?

If it's not a good fit in the documentation, a blog post explaining the different optimizations in the sort package (if the data is small, we use this algorithm; large, this algorithm, here are the experiments we tried that weren't faster, etc.) might be neat.