title: Which sorting algorithm is best suited to re-sort an almost fully sorted list?
body: <p>I have a list of strings which has been sorted by a specific comparison function.</p>
  
  <p>Now I have to re-sort this list using a <em>different</em> comparison function. </p>
  
  <p>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.</p>
  
  <p>Which sorting algorithm is best suited to re-sort this almost fully sorted list in terms of runtime execution speed? </p>