基于比较的排序算法复杂度的理论下界为 O(nlog n)，同时指出了：
每一次判定 a < b ，都相当于回答了一次「是否问题」。按照已有的知识，若要尽可能快地完成排序，就要让每一次大小判断的结果落在两种答案之一的概率接近；若不然，则这次比较带来的信息量较小，也就需要更多次的比较来完成排序。
此篇建立在这些知识的基础上，首先探讨以下三个问题，而后引出号称「在所有情况下，都能较快完成排序任务的内省式排序（Introspective Sort）」：
- 为什么堆排序一般快不过快速排序？
- 快速排序快得无懈可击吗？
- 插入排序什么时候快？
为什么在平均情况下快速排序比堆排序要优秀
堆排序是渐进最优的比较排序算法，达到了O(nlgn)这一下界，而快排有一定的可能性会产生最坏划分，时间复杂度可能为O(n^2)，那为什么快排在实际使用中通常优于堆排序？
- 虽然quick_sort会n^2（其实有稳定的nlgn的版本），但这毕竟很少出现。heap_sort大多数情况下比较次数都多于quick_sort，尽管大家都是nlgn。那就让倒霉蛋倒霉好了，大多数情况下快才是硬道理。
- 堆排比较的几乎都不是相邻元素，对cache极不友好，这才是很少被采用的原因。数学上的时间复杂度不代表实际运行时的情况.快排是分而治之，每次都在同一小段进行比较，最后越来约接近局部性。反观堆排，堆化过程中需要一直拿index的当前元素A和处于index*2 + 1 的子元素B比较, 两个元素距离较远。(局部性原理是指CPU访问存储器时，无论是存取指令还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续区域中。)
- 在快排的迭代过程中，我们所处理的 [比基准大的数]，[比基准小的数] 序列中，在进行两个数之间大小比较时，在该局部范围内，产生“大于”或者“小于”的可能性是一样的。这意味着每比较一次必然会产生一次有意义的比较结果，会缩减接下来迭代的扫描工作量。
- 我们再来看看堆排序。在每一次进行重新堆调整的时候，我们在迭代时其实就已经知道，上一层的结点值一定是比下面大的。为了打乱堆结构把最后一个元素与顶堆互换时，此时我们也已经知道，互换后的元素是一定比下一层的数要小的。而在迭代时为了调整堆我们还是要进行一次已经知道结果的比较，这无疑是没有什么价值的，也就是产生了一次没有意义的比较，对接下来的迭代工作量并没有任何进展。
回顾三种排序算法
堆排序慢在哪
首先回顾一下堆排序的大致流程：
- 在未排序部分建堆——一棵二叉树，父节点总是比子节点大；
- 将堆顶元素与最后一个未排序元素兑换；
- 回到 1，直至排序完成。
这里需要注意，在用数组实现的堆当中，父节点 i 的左右子节点的位置分别是 2i + 1 与 2i + 2,
按照前述的原则，不难发现，堆底元素几乎是必然要小于堆顶元素的两个子节点元素。因此，在重新建堆时，原本的堆底元素与上述两个元素的比较 a < b 成立的概率几乎为 0。这就意味着，在堆排序中，存在诸多类似这样「不平衡」的判断，而这些判断带来的信息量很小，因此需要额外的比较次数来提供足够的信息量。
这就是堆排序不够快的原因。具体来说，尽管在平均情况下，堆排序的时间复杂度与快速排序都是 O(nlog n)，但是它时间复杂度的常数项要比快速排序大不少。不过，由于堆排序所需的比较次数是恒定的，所以它在最坏的情况下，复杂度也是 O(nlog n)。这算是堆排序的一个优点。
快速排序也没有快得无懈可击
快速排序的核心是选取主元（pivot），而后将小于主元的元素置于左边以及大于等于主元的元素置于右边，而后递归这个过程。
现在我们来看元素 a 的比较过程。在全部 n! 种排列中，满足 a < pivot 的排列有一半，不满足的也有一半。因此这次比较干掉了一半的可能性，nice shot！
不失一般性，现在假定 a < pivot 成立，我们来看元素 b 的比较过程。在剩下的 frac{n!}{2} 种排列中，满足 b < a < pivot 、 a < b < pivot 和 a < pivot < b 的各占三分之一。这也就是说，若是 b < pivot ，则这一次判断只能排除剩下的三分之一的可能性。这次比较的效果，就不那么令人满意了。
继续下去，则每次比较所能获得的信息量会逐渐下降，距离最优的情形越来越远。特别地，若是 pivot 是序列中最大或最小的元素，则这一次分割没有排除任何可能性——完全是白费功夫。这就是为什么说快排也不是快得无懈可击，以及这就是为什么说 pivot 选择最值时是快速排序的最坏情况。
插入排序在几乎排好序的序列上很快
插入排序某种意义上是最生动的排序算法了。在玩扑克牌的时候，大多数人都会使用插入排序的办法，将分派到自己的扑克牌按顺序整理好。
对于一个几乎已经排好序的序列（逆序对很少），使用堆排或快排仍然能达到 O(nlog n) 的时间复杂度。但是插入排序在这种情况下，只需要从头到尾扫描一遍，交换、移动少数元素即可；时间复杂度近乎 O(n)。究其原因，堆排或快排按照各自的要求，将已经近似排好序的序列打乱，而后又排序整理，没有用到「几乎已经排好序」的先验知识，所以在这种情况下不如插入排序快就是自然的了。
内省式排序（Introspective Sort）
回顾上一节的内容，我们发现：
- 快速排序在大多数情况下效率最高，应当是首选的排序算法。但是它在某些情况下，会掉入陷阱，复杂度恶化到 O(n^2)。
- 堆排序虽然在大多数情况下不如快速排序效率高，但在所有的情况下复杂度都是 O(nlog n)。因此若能检测到快速排序掉入陷阱，则堆排序会是一个很好的补充。
- 插入排序虽然复杂度虽然只能达到 O(n^2)，但若能已知「几乎已经排好序」，切换到插入排序的效率又要比快速排序和堆排序高出不少，能做到 O(n)。
显然，三种排序各有优点也各有缺点。若能将它们的优点组合起来，同时避免它们各自的缺点，形成内省式排序，那就能做到在所有情况下都能以较快的速度完成排序任务了。
不难归纳，这样的内省式排序，策略应该如下：
- 在数据量足够大的情况使用快速排序；
- 在快速排序掉入陷阱时，主动切换到堆排序；
- 在快速排序和堆排序已经做到基本有序的情况下，或者数据量较小的情况下，主动切换到插入排序。
于是，问题就变成了，如何定义数据量足够大或者说基本有序，以及如何确定快速排序掉入了陷阱，而对效率没有伤害。现在我们来解决这些问题，从而完善整个内省式排序。
数据量足够大或者基本有序是什么意思？
一般来说，当递归调用带来的开销大于递归调用后实际操作的开销时，调用快排、堆排就不太恰当了。因此，如果存在一个阈值，当待排序元素的数量小于该阈值时递归调用的开销相对较大，则该阈值的大小应当取决于机器硬件的特性（位宽、cache 性能）和待排序元素本身的特性（体积、是否对缓存友好）。
这一阈值某种意义上可以算作是算法的「超参数」，它不会在算法执行时带来额外的开销。
如何确定快速排序掉入了陷阱？
通过上文的分析，我们知道，快速排序的效率主要取决于 pivot 的选择。若 pivot 恰好是待分割区间内的最大值或最小值，则这种分割没有排除任何可能的排序，因而是白费力气。既然如此，那么最平凡的方式，就是去检查所选的 pivot 是否为待分割区间内的最值即可判定快速排序是否掉入了陷阱。
然而，判定区间最值的问题，不可避免地要遍历区间内的所有元素。这也就是说，我们为了避免快速排序掉入陷阱，而使得复杂度从 O(nlog n) 恶化到 O(n^2)，我们在每一次递归中，都要遍历一次所有元素。这相当于额外增加了 O(nlog n) 的遍历操作。诚然，整个算法还是 O (nlog n) 的复杂度，但是无疑增加了常数倍数。考虑到我们的指导原则之一就是尽可能在大多数情况下，避免常数高的堆排序；主动去推高时间常数的做法是不可取的。
行文至此，我们又需要转换一次看待问题的角度。正如数学中有「正难则反」的说法。
我们来回顾一下计算机上的「杀毒软件」。早期的计算机病毒，更新速度较慢；但计算机「小白」太多，所以病毒的威力还是很大的。这时候的杀毒软件，会对病毒样本进行脱壳、反编译分析等操作，获取病毒的特征代码，而后加入特征库中。杀毒软件将更新的特征库分发给用户后，用户的杀毒软件就有能力查杀新的病毒了。这种方式的优点是精准，不易误杀；但是缺点也很明显——滞后性。
为了解决这个问题，后来反病毒工程师就想了一个办法。我们说，判断一个事物可以有两种思路。一个是判断其本质特征，例如使用特征码判断病毒；二个是观察其行为特性。对于病毒来说，它总是要潜伏下来搞破坏的，所以必然有某些行为特征。杀毒软件可以利用这些行为特征来判断一个可执行文件是否是计算机病毒。而这件事情是可以不依赖中心服务器，交由杀毒软件客户端自己处理的。这就解决了传统杀毒软件滞后性的问题。
杀毒软件的例子应当给予我们有一些启发。既然正面处理问题有困难，那就反过来，看看快速排序掉入陷阱会有什么行为特征。这似乎也不难，是显而易见的。快速排序调入陷阱，意味着在递归时快速排序算法会连续多次选中带分割区间的最值元素，从而导致多次「无效」分割，进而导致递归层数快速增加。因此，我们可以设置一个阈值；一旦递归深度超出该阈值，则认为快速排序掉入陷阱了并切换到堆排序算法。
快速排序在理想状态下，应当递归约 log n 次。因此，我们可以说，如果递归深度明显大于 log n，快速排序就掉进陷阱了。于是，我们可以将该阈值设置为 log n 的某一倍数，比如 2log n；一旦递归深度超过 2log n，就从快速排序切换到堆排序。