内省排序为何在快速排序过深时切换算法

内省排序由大卫·穆塞尔在1997年提出，是结合快速排序和堆排序的比较排序算法。它先使用通常效率较高的快速排序，同时观察递归深度，当深度超过与数据规模对数相关的阈值时，改用堆排序处理。

这样设计的原因在于快速排序受基准点选择影响。如果划分持续失衡，递归会变深，最坏时间可能退化至平方级。即使从首、中、尾元素取中位数，也不能排除专门构造的序列造成不良划分。

切换到堆排序后，算法能够将整体最坏时间约束在O(n log n)，同时保留快速排序在常见数据上的优势。内省这个名称强调算法会检查自身执行状态，而非无条件坚持一种方法。它解决的是性能边界问题，不意味着每组输入都一定比所有其他排序更快。

资料依据：维基百科《内省排序》及该页贡献者（修订记录）。本文重组论述并改写表达；依Creative Commons Attribution-Share Alike 4.0提供。