algorithm - 哪种排序算法使用最少的比较？

Question

想象一下比较两个元素的成本非常高的情况。

您会使用哪种排序算法？

哪种排序算法在平均情况下使用最少的比较？

如果您可以预期很多比较元素是相同的，比如说 80% 的比较。有区别吗？

Answer 1

Merge-insertion sort 是插入排序的一种变体，几十年来一直被吹捧为已知比较次数最少的排序算法，并且可能仍然是可自由记录的最佳比较次数最少的排序算法:

Merge-insertion sort is the sorting algorithm with the minimum possible comparisons for n items whenever n ≤ 15 or 20 ≤ n ≤ 22, and it has the fewest comparisons known for n ≤ 46.

Glenn K. Manacher's algorithm据报道，“以及后来打破记录的排序算法”(不幸的是，目前似乎没有任何算法被自由记录)采用合并插入排序算法以提供更少的比较。