能否依据as-if规则为int*特化的std::sort使用冒泡排序？

结论 #

哪怕是无自定义谓词的int*特化版本，用冒泡排序实现std::sort也完全不符合C++标准要求。

规则说明 #

• C++标准对std::sort有明确的强制复杂度约束：比较次数必须达到O(n log n)量级。这个约束对所有重载/特化版本的std::sort都生效，和元素类型、是否使用默认谓词、迭代器是否为指针类型没有关系。
• 你提到的「用户无法观测比较次数、迭代次数」的前提不影响规则的有效性：复杂度要求是标准对标准库实现方的硬性语义要求，和用户能不能观测到操作的副作用无关，不存在「用户观测不到就可以违反规则」的空间。

关于你实际关心的核心问题 #

即「标准库实现方是否被允许做时间复杂度更差但实际运行速度更快的优化」，答案是完全不被允许。
标准给出通用算法的复杂度要求，核心作用就是给所有开发者提供稳定的性能下限预期，避免实现方为了极端小众的场景优化，破坏绝大多数通用场景下的性能表现。哪怕某个O(n²)的实现在长度极小的序列下实际运行速度比O(n log n)的实现更快，也不能违反标准规定的复杂度要求。

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