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

Question

I have list which is sorted using a specific string comparison function.

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

This new comparsion is 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?

Answer 2

Have access to both search operations? If yes, you can to build some hash tree during first sorting process and use it to other sort operations

Answer 3

As I understood your data list is allready sorted (let say by ascii/country charset order), but without some dictionary rules applied for particular country. For example Germany and their Umlauts

see Germanic_umlaut in wikipedia

you are not inserting new items, you just want to resort them by little bit more strict sorting rule.

as you can read for example here

http://www.softpanorama.org/Algorithms/Sorting/bubblesort.shtml

bubble sort works well on allready sorted lists with just a few permutations. This sounds like bubble sort is good algorithm to start with. Also note that bubble sort is "stable" sorting algorithm. This could be important for your scenario.