内省排序（英语：Introsort）是由David Musser在1997年设计的排序算法。这个排序算法首先从快速排序开始，当递归深度超过一定深度（深度为排序元素数量的对数值）后转为堆排序。采用这个方法，内省排序既能在常规数据集上实现快速排序的高性能，又能在最坏情况下仍保持O(n log n)的时间复杂度。由于这两种算法都属于比较排序算法，所以内省排序也是一个比较排序算法。
简介
内省排序又称Introsort，是一个相当偏门的排序算法，是由David Musser在1997年设计出来的。属于比较排序算法的一种。
内省排序的实现过程是这样的，首先由快速排序开始，当递归深度超过一定程度时，转换为堆排序。所以内省排序既能在常规数据集上实现快速排序的高性能，又能在最坏情况下仍保持O(N log N)的时间复杂度。
在快速排序算法中，一个关键操作就是选择基准点（pivot）：元素将被此基准点分开成两部分。最简单的基准点选择算法是使用第一个或者最后一个元素，但这在排列已部分有序的序列上性能很糟。Niklaus Wirth为此设计了一个快速排序的变体，使用处于中间的元素来防止在某些特定序列上性能退化为O(N^2)的状况。这个3基准中位数选择算法从序列的第一，中间和最后一个元素取得中位数来作为基准，虽然这个算法在现实世界的数据上性能表现良好，但经过精心设计的序列仍能大幅降低此算法性能。这样就有攻击者精心设计序列发送到因特网服务器以进行拒绝服务（DOS）攻击的潜在可能性。
Musser研究指出，在为3基准中位数选择算法精心设计的100,000个元素序列上，introsort的运行时间是快速排序的1 / 200。在Musser的算法中，最终较小范围内数据的排序由Sedgewick提出的小数据排序算法完成。此外，内省排序在处理较小数据集时会切换到插入排序以提高效率，SGI的C++标准模板库在其stl_algo.h文件中采用了Musser的内省排序算法，其中切换到插入排序的数据量阈值设定为16个元素。这一实践进一步提升了内省排序在实际应用中的性能和效率。