Introsort

概述

Introsort（Introspective Sort，内省排序） 是由 David R. Musser 于 1997 年提出的一种混合排序算法，结合了 快速排序、堆排序 和插入排序的优点，在最坏情况下仍能保证 $O(n\lg n)$ 的时间复杂度。

定义

Introsort

Introsort 是一种混合排序算法，工作流程如下：

1. 初始阶段：使用 快速排序 对数组进行排序。
2. 递归深度监控：在排序过程中持续监控递归深度。
3. 退化检测：当递归深度超过 $2\lceil \lg n\rceil$ 时，判定快速排序可能退化为 $O(n^2)$，此时切换为 堆排序 来保证最坏情况性能。
4. 小数组优化：当子数组规模足够小时（通常 $\le 16$），切换为插入排序，因为对小数组插入排序的常数因子更优。

最坏时间复杂度：$O(n\lg n)$ 平均时间复杂度：$O(n\lg n)$ 空间复杂度：$O(\lg n)$

核心性质

设计动机

纯快速排序的最坏情况为 $O(n^2)$，虽然随机化可以降低概率，但无法完全消除。Introsort 通过”内省”（introspective）机制检测退化情况并切换算法，在保持快速排序平均性能的同时，保证最坏情况的渐近最优。

递归深度阈值

选择 $2\lceil \lg n\rceil$ 作为递归深度阈值的原因：

• 理想情况下快速排序的递归深度为 $\lceil \lg n\rceil$。
• $2\lceil \lg n\rceil$ 给予了足够的容错空间，不会在正常情况下误触发切换。
• 超过此阈值几乎可以确定发生了退化。

C++ std::sort 的实现

Introsort 是 C++ 标准库 std::sort 的底层实现算法（自 C++ 标准化以来）。它提供了：

• 与快速排序相当的平均性能。
• $O(n\lg n)$ 的最坏情况保证（满足标准要求）。
• 原地排序（$O(\lg n)$ 额外空间）。

与其他混合排序的对比

算法	组合策略	最坏时间
Introsort	快速排序 + 堆排序 + 插入排序	$O(n\lg n)$
Timsort	归并排序 + 插入排序	$O(n\lg n)$
纯快速排序	仅快速排序	$O(n^2)$

章节扩展

第7章：快速排序

Introsort 是快速排序的工程化改进，通过结合堆排序来弥补快速排序最坏情况的不足。CLRS 第7章的习题 7-5 探讨了这一主题。

参见

• 快速排序
• 堆排序
• 插入排序