GCC中std::sort对已初始化有序向量调用比较器两次的机制与原因问询

大家好，我最近在调试C++11里std::sort配合lambda比较器的行为时，碰到了一个有点反直觉的情况，想请各位帮忙分析下背后的原因。

测试场景与环境 #

我写了一段简单的测试代码，分别对初始无序和初始已升序的两个vector调用std::sort，并且在lambda比较器里打印每次比较的参数，用来追踪std::sort的调用逻辑。编译环境是C++11标准的GCC/Clang，全程没有开启任何优化选项。

测试代码 #

#include <iostream>
#include <vector>
#include <algorithm>

void print(std::string&& title_, const std::vector<int> v_) {
    std::cout << title_;
    for(auto&& n : v_)
        std::cout << n << " ";
    std::cout << std::endl;
}

int main() {
    // 测试初始无序的向量
    std::vector<int> t1 = { 32 , 0 };
    std::sort( std::begin(t1), std::end(t1),
        []( int v1_, int v2_ ) {
            std::cout << "\tv1 = " << v1_ << " , v2 = " << v2_ << std::endl;
            return (v1_ < v2_);
        }
    );
    print("(After) t1 : ", t1);
    std::cout << "----------------" << std::endl;

    // 测试初始已升序的向量
    std::vector<int> t2 = { 0 , 32 };
    std::sort( std::begin(t2), std::end(t2),
        []( int v1_, int v2_ ) {
            std::cout << "\tv1 = " << v1_ << " , v2 = " << v2_ << std::endl;
            return (v1_ < v2_);
        }
    );
    print("(After) t2 : ", t2);
}

实际输出结果 #

运行后得到的输出如下：

v1 = 0 , v2 = 32
(After) t1 : 0 32 
----------------
        v1 = 32 , v2 = 0
        v1 = 32 , v2 = 0
(After) t2 : 0 32 

我的核心疑问 #

对比两个测试用例的结果，我发现了很奇怪的差异：

• 初始无序的t1，std::sort只触发了1次比较器调用
• 但初始已经是升序的t2，居然触发了2次比较器调用
• 我还额外测试了3个元素的有序vector，结果比较器被调用了4次，比无序场景的调用次数还多

我甚至去查看了两次std::sort调用的汇编代码，外层的包装函数几乎完全一致，找不到能直接解释这个差异的线索。所以想请教各位：GCC的std::sort底层实现到底是什么逻辑，会导致已经有序的数组反而让比较器被调用更多次呢？

内容来源于stack exchange