哪种排序算法的已知平均情况比较次数表现最优？

归并排序不是已知平均比较次数最优的基于比较的排序算法，存在更优的算法。

具体说明： #

• 归并排序的平均比较次数约为 n log₂n - n + O(log n)，已经非常接近基于比较排序的平均比较次数理论下界（下界为 n log₂n - n + O(log n)），但仍有算法在平均场景下表现更优：
  • Timsort：归并排序的优化变体，融合了插入排序逻辑，针对实际场景中常见的部分有序数组做了针对性优化，平均比较次数远低于普通归并排序，是Python、Java等主流语言标准库的默认排序实现。
  • 随机快速排序：虽然理论平均比较次数系数（约1.386）略高于归并排序，但由于缓存局部性更好、内存访问开销更低，实际运行中的平均性能往往优于归并排序。
  • 库排序（Library Sort）：通过预留间隙的方式优化插入操作，平均比较次数和移动次数都比归并排序更优，不过需要额外的空间开销。
• 补充背景：Ford–Johnson算法（归并插入排序）的优势在最坏情况比较次数（已知最优），但它的平均性能反而不如普通归并排序，和问题中的描述一致。

内容的提问来源于stack exchange，提问作者Vilim Lendvaj