面试真题

结论：std::sort通常实现为内省排序（introsort），混合快速排序、堆排序和插入排序。原理：1. 先以快排递归分区；2. 当递归深度超过2*log2(N)时改用堆排，避免快排最坏O(N^2)；3. 数据量小（如N<16）用插入排序减少调用开销。复杂度：平均与最坏均为O(N log N)，空间O(log N)。标准仅要求平均O(NlogN)且应合理，并非单纯快排，以此兼顾效率与稳定。示例：对百万级随机序列，先快排后可能切堆排，小段插排。