Rust排序比较次数少得惊人？背后原因探究

Rust标准库中的slice::sort采用的是Timsort算法——这是一种针对真实世界数据优化的混合排序算法，融合了归并排序和插入排序的特性。

为什么有序输入的比较次数极少？ #

• Timsort会先扫描输入，识别其中已有的连续有序段（称为"run"）。对于完全有序的向量，整个数组就是一个完整的run，不需要进入后续的归并或大量插入排序流程。
• 长度为2的有序向量：算法会直接判定其已有序，无需执行任何比较操作（这是小长度数组的特殊优化逻辑）。
• 长度为n的有序向量：仅需n-2次比较完成"整体有序"的验证（这是预扫描阶段的实现细节，目的是快速跳过不必要的排序操作）。

为什么不符合O(nlogn)的预期？ #

O(nlogn)是该排序算法的最坏时间复杂度，而Timsort的核心优势就是优化有序/部分有序的输入场景，它的最好时间复杂度为O(n)。当输入本身已经完全有序时，算法只需要线性扫描验证有序性，不需要执行O(nlogn)级别的比较与交换，这完全符合算法的设计目标。

如果想验证平均/最坏情况的表现，可以测试打乱后的向量，此时比较次数会趋近于O(nlogn)的量级。

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