哪种排序算法最适合对几乎完全排序的列表进行重新排序？

我有一个按特定比较功能排序的字符串列表。

现在，我必须使用其他比较功能对列表进行重新排序。

当比较某些特殊字符（例如Umlauts）时，此新的比较功能的行为会稍有不同。在大多数情况下，元素仅需移动一个或两个槽即可到达正确位置。

哪种算法" title="排序算法">排序算法最适合在运行时执行速度方面对几乎完全排序的列表进行重新排序？

插入排序适用于较小或几乎排序的列表。

从这份ACM论文中：

对列表长度和较小排序率的各种组合的随机生成列表进行的测试表明，对于较小或非常接近排序的列表，“直接插入排序”是最佳选择，否则，“快速排序”是最佳选择。

从维基文章插入排序：

如果输入数组已经排序，则插入排序执行的n-1个比较少，因此，在给定排序或“几乎排序”的数组时，插入排序会更有效。