一、std::sort 内部实现
std::sort 不是单纯的快排，而是内省排序：
// 伪代码
void sort(iterator first, iterator last) {
if (last - first < 16) {
insertion_sort(first, last); // 小数组用插入排序
return;
}
int depth_limit = 2 * log2(last - first);
intro_sort_loop(first, last, depth_limit);
// 如果 depth_limit 达到 0，说明快排退化，切换到堆排序
}
void intro_sort_loop(iterator first, iterator last, int depth) {
while (last - first > 16) {
if (depth == 0) {
make_heap(first, last); // 切换到堆排序
sort_heap(first, last);
return;
}
depth--;
iterator cut = partition(first, last); // 快排分区
intro_sort_loop(cut + 1, last, depth); // 递归大的一边
last = cut; // 尾递归处理小的一边
}
}
组合策略：快排（通用最快）+ 堆排（退化保护）+ 插入排序（小数组最优）。
二、面试追问 Q&A
Q1：N 很小时为什么插入排序比快排快？ A：快排有函数调用开销（partition 中的循环 + 递归），N 很小时这些开销占比大。插入排序对小于 16 的数组，没有递归，分支预测好，实际更快。
Q2：std::stable_sort 和 std::sort 怎么选？
A：不需要稳定就用 std::sort（更快）。需要稳定（相等元素的相对顺序不变）用 std::stable_sort。