What algorithms use fewer comparisons than merge-insertion sort?

Question

On the Wikipedia page for Merge-Insertion Sort it says

Manacher's algorithm and later record-breaking sorting algorithms have all used modifications of the merge-insertion sort ideas.

in reference to sorting algorithms that use the fewest comparisons. But it does not explain what algorithms it's referring to. The page the citation links to also just says "other algorithms".

Answer 1

"Other algorithms" doesn't necessarily mean "other practical implementations". M-I is still essentially the theoretical best in terms of comparisons made for an infinite number of elements to sort. That's just as long as you don't have to worry about implementation, memory use, or any other real world concerns.

The other algorithms are improvements to merge insertion rather than completely different concepts. They use small tweaks like changing the order elements are compared or inserting two elements together more efficiently. This paper discusses the worst cases.

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.

For curiosity, here are some worst-case numbers for the merge-insertion variations from the paper linked above:

• n log n ? 1.4427n + O(log n) - Lowest mathematically possible
• n log n ? 1.3999n + o(n) - Ford-Johnson Merge-Insertion (original)
• n log n ? 1.4005n + O(n) - Iwama-Teruyama Merge-Insertion (1,2-insertion)