std::sort的核心设计思想
C++标准库中的std::sort函数采用了一种称为内省排序(IntroSort)的混合算法，巧妙结合了三种经典排序算法的优势：
不同规模数据下的工作原理
小规模数据 (n ≤ 16)
算法选择：插入排序 (InsertionSort)
工作原理：通过将每个元素插入到已排序序列的正确位置来工作。对于小规模数据，插入排序的交换次数和比较次数都很少，且没有递归开销。
示例：
输入
23 13 3 45 5，std::sort会直接用插入排序处理，按比较函数的规则（个位→数值）排列，效率极高。
中等规模数据 (16 < n ≤ 1e5)
算法选择：快速排序为主，插入排序收尾
工作原理：选择一个pivot（通常用三数取中），将数组分成小于pivot、等于pivot、大于pivot的三部分，递归处理左右子数组。当子数组长度小于16时，切换为插入排序。
特点：
快速排序的平均时间复杂度为O(n log n)，且cache友好（数据在内存中的访问顺序与排序顺序一致，减少缓存未命中）。
大规模数据 (n > 1e5 或递归深度超过阈值)
算法选择：快速排序→堆排序→插入排序
工作原理：当递归深度超过2*log2(n)时，停止快速排序并切换为堆排序。堆排序将当前未排序的子数组转换为最大堆（或最小堆），然后反复提取堆顶元素。
特点：
堆排序的作用是避免快速排序的最坏情况（如有序数组、逆序数组或所有元素相同的数组）。对于大规模数据，堆排序的稳定性比快速排序更重要。
| 数据规模 | 主要算法 | 时间复杂度 | 原因说明 |
|---|---|---|---|
| 小规模 (n≤16) | 插入排序 | O(n²) | 常数极小，无递归开销，比快速排序/堆排序更快 |
| 中等规模 (16 | 快速排序 | O(n log n)（平均） | 平均效率高，cache友好，适合中等规模数据 |
| 大规模 (n>1e5) | 快速排序→堆排序 | O(n log n)（最坏） | 避免快速排序的O(n²)最坏情况，堆排序保证稳定的O(n log n)性能 |
std::sort通过混合排序算法，在不同规模数据下都能达到最优的时间复杂度和实际运行速度。对于中等规模数据（如题目中的n≤1e4），std::sort能高效处理，只要比较函数正确，就能满足题目要求。