Which sorting algorithm is best suited to re-sort an almost fully sorted list?

Question

I have a list of strings which has been sorted by a specific comparison function.

Now I have to re-sort this list using a different comparison function.

This new comparison function behaves slightly different when comparing certain special characters, like Umlauts for example. In most cases the element has to be moved just one or two slots to get to the correct position.

Which sorting algorithm is best suited to re-sort this almost fully sorted list in terms of runtime execution speed?

Answer 1

Insertion sort works well on small or nearly sorted lists.

From this ACM Paper:

Tests on randomly generated lists of various combinations of list length and small sortedness ratios indicate that Straight Insertion Sort is best for small or very nearly sorted lists and that Quickersort is best otherwise.

From wiki article Insertion sort:

If the input array is already sorted, insertion sort performs as few as n-1 comparisons, thus making insertion sort more efficient when given sorted or "nearly-sorted" arrays.

SO Question: Is there ever a good reason to use Insertion Sort?