std::sort 的底层通常采用内省排序。内省排序不是单一算法，而是快速排序、堆排序和插入排序的组合：递归深度较浅时使用快速排序，递归过深时切换为堆排序，区间较小时改用插入排序。无论切换成哪种算法，元素之间的先后顺序都由自定义比较函数决定。比较函数表面上是返回两个元素谁在前谁在后，实际上它必须提供一个稳定的、一致的小于关系。这个关系在 C++ 标准中被称为严格弱序。
严格弱序包含四条规则：非自反、非对称、传递，以及等价关系的传递。非自反表示任何元素不能小于自己；非对称表示如果 a 小于 b，那么 b 不能小于 a；传递表示如果 a 小于 b 且 b 小于 c，则 a 小于 c。最后一条等价传递稍微抽象，它要求那些互相不小于对方的元素可以视为等价，并且等价关系自身也必须传递。只要比较器满足这四条，排序算法就能把元素安全地组织成升序。如果其中任意一条被破坏，算法内部的划分边界、堆调整或插入位置都会出现错误，轻则排序结果错误，重则越界崩溃。
一、排序算法如何依赖严格弱序
快速排序的分区过程最能说明问题。分区函数会选定一个主元，然后扫描当前区间：如果 comp(当前元素, 主元) 返回 true，就把它划分到左边；否则划分到右边。这里默认 comp 表达的是严格小于。假设比较器写成 return a.key <= b.key，那么当元素和主元键值相等时，comp(当前元素, 主元) 和 comp(主元, 当前元素) 都会返回 true。同一个元素既被认为小于主元，也被认为大于主元，分区左右边界互相矛盾。扫描过程中迭代器可能回退过头，最终访问到 begin 之前的内存。
堆排序对比较器的依赖同样强。建堆时，父节点与子节点的大小关系决定是否交换。如果比较器在父子之间返回不稳定结果，堆的完全二叉树性质会被破坏，向下调整可能越过数组末尾。插入排序则通过比较器判断元素是否需要前移，错误的比较条件可能让内层循环一直满足，滑动位置越过第一个元素，形成越界写。
因此，std::sort 并不检查比较器是否合法。标准库把这一责任完全交给调用者。比较器不符合严格弱序时，程序进入未定义行为，任何表现都可能出现：有时小数据量下看起来正常，一旦数据规模、初始顺序或算法切换条件变化，就会突然崩溃。这也是为什么同样一份错误比较函数在不同环境下表现不一致。
二、典型错误比较函数与崩因
第一种错误是用小于等于代替严格小于。下面这个比较函数在键值相等时会返回 true：
#include <vector>
#include <algorithm>
#include <iostream>
struct Item {
int key;
int value;
};
bool bad_cmp(const Item& a, const Item& b) {
// 错误：小于等于破坏了非自反性
return a.key <= b.key;
}
int main() {
std::vector<Item> items = {{3, 1}, {3, 2}, {1, 5}, {2, 4}};
std::sort(items.begin(), items.end(), bad_cmp);
for (const auto& it : items) {
std::cout << it.key << ":" << it.value << " ";
}
}
键值相同的情况下，bad_cmp(a, a) 返回 true，违反非自反。排序算法在处理重复键时可能来回交换同一批元素，分区边界无法稳定。实际运行可能不会立即报错，但每次调用都在踩未定义行为的边界。修复方法很简单，把 <= 改成 <，相等元素保持相对顺序。
第二种错误是逻辑不对称。例如有人根据特殊值提前返回，导致 comp(a, b) 与 comp(b, a) 可能同时为 true：
bool asym_cmp(const Item& a, const Item& b) {
if (a.key == 0) return false;
if (b.key == 0) return true;
return a.key < b.key;
}
当 a.key 和 b.key 都非零且相等时，返回 false，没问题；但如果一个键为 0，逻辑就可能破坏对称或传递。比如 a.key=0、b.key=0 时，a 与 b 比较会先进入 if (a.key == 0) 返回 false，b 与 a 比较也返回 false，看起来等价；可如果引入第三个元素 c.key=0，等价关系在传递性上可能不成立。排序算法一旦在数组中间遇到这种不一致，后续路径就会跑偏。
第三种错误是依赖外部可变状态。比较函数若读取全局变量、当前时间或随机数，排序过程中比较结果可能随调用顺序变化。标准库没有限定比较次数，可能这次 comp(a, b) 是 true，下次同样输入又是 false。这样所有算法假设都会作废，崩溃也许不会立刻出现，但结果一定不可靠。
三、编写与验证严格弱序比较器
安全比较函数的核心只有一条：明确返回严格小于，而不是小于等于，也不是大于等于。多字段排序时建议使用 std::tie 组合字段，因为 tuple 的 operator< 已经实现了严格弱序。以下示例先按部门，再按姓名，最后按工资排序：
#include <tuple>
#include <string>
struct Employee {
int department;
std::string name;
int salary;
};
bool emp_cmp(const Employee& a, const Employee& b) {
return std::tie(a.department, a.name, a.salary)
< std::tie(b.department, b.name, b.salary);
}
如果需要降序，可以交换比较方向，但要保持一致性。正确写法是 return a.key > b.key，而不是 return a.key >= b.key。大于关系和小于关系在严格弱序下是对偶的：a 大于 b 可以看作 b 小于 a。只要比较器始终用同一方向，并且不把等于包含进去，就能满足要求。
开发阶段可以写一个简单的检查函数，对容器中的元素做非自反和非对称断言。虽然不能覆盖传递性，但能提前暴露大量低级错误：
#include <cassert>
#include <vector>
template <typename T, typename Comp>
void check_strict_weak(const std::vector<T>& data, Comp comp) {
for (const auto& a : data) {
assert(!comp(a, a)); // 检查非自反
for (const auto& b : data) {
if (comp(a, b)) {
assert(!comp(b, a)); // 检查非对称
}
}
}
}
这个函数在调试模式下可以帮助快速定位问题。对于传递性，可以再增加三重循环：若 comp(a, b) 和 comp(b, c) 为 true，则 comp(a, c) 必须为 true。不过要注意复杂度，只适合小数据量或单元测试。发布版本中不应保留这些检查，以免影响性能。
除了断言，代码评审时也要关注比较器是否读取了外部状态，是否遗漏分支，是否包含等于号。稍微多花一点时间确认严格弱序，比线上程序随机崩溃要划算得多。