哪些算法比合并插入排序使用更少的比较？
What algorithms use fewer comparisons than merge-insertion sort?
在 Merge-Insertion Sort 的维基百科页面上说
Manacher's algorithm and later record-breaking sorting algorithms have all used modifications of the merge-insertion sort ideas.
参考使用最少比较的排序算法。但它没有解释它指的是什么算法。引文链接到的页面也只是说“其他算法”。
“其他算法”并不一定意味着“其他实际实现”。 M-I 在对无限数量的元素进行排序的比较方面基本上仍然是理论上最好的。只要您不必担心实现、内存使用或任何其他现实问题。
其他算法都是对合并插入的改进，而不是完全不同的概念。他们使用一些小的调整，例如更改比较元素的顺序或插入 two elements together more efficiently. This paper 讨论最坏的情况。
Timsort uses similar concepts (specifically in merging runs of already-sorted data in "galloping mode") but it's more focused on performance in real-world data than asymptotic complexity on infinite random inputs. Block sort is another fancy algorithm that actually sorts in-place but I don't have a comparison count at the moment. It's implemented in Wikisort and Grailsort.
出于好奇，这里有一些 worst-case 数字来自上面链接的论文的 merge-insertion 变体：
n log n − 1.4427n + O(log n) - 数学上可能的最低值n log n − 1.3999n + o(n) - Ford-Johnson Merge-Insertion（原创）n log n − 1.4005n + O(n) - Iwama-Teruyama Merge-Insertion (1,2-插入)
在 Merge-Insertion Sort 的维基百科页面上说
Manacher's algorithm and later record-breaking sorting algorithms have all used modifications of the merge-insertion sort ideas.
参考使用最少比较的排序算法。但它没有解释它指的是什么算法。引文链接到的页面也只是说“其他算法”。
“其他算法”并不一定意味着“其他实际实现”。 M-I 在对无限数量的元素进行排序的比较方面基本上仍然是理论上最好的。只要您不必担心实现、内存使用或任何其他现实问题。
其他算法都是对合并插入的改进，而不是完全不同的概念。他们使用一些小的调整，例如更改比较元素的顺序或插入 two elements together more efficiently. This paper 讨论最坏的情况。
Timsort uses similar concepts (specifically in merging runs of already-sorted data in "galloping mode") but it's more focused on performance in real-world data than asymptotic complexity on infinite random inputs. Block sort is another fancy algorithm that actually sorts in-place but I don't have a comparison count at the moment. It's implemented in Wikisort and Grailsort.
出于好奇，这里有一些 worst-case 数字来自上面链接的论文的 merge-insertion 变体：
n log n − 1.4427n + O(log n)- 数学上可能的最低值n log n − 1.3999n + o(n)- Ford-Johnson Merge-Insertion（原创）n log n − 1.4005n + O(n)- Iwama-Teruyama Merge-Insertion (1,2-插入)