内观排序（introsort)是快速排序的一种改进形式，即C++中的std::sort()

在实践中，快速排序的速度很快的，不足的地方是在某些情况下，速度会很慢。原因是切分原素选取不合理，使得切分出来的两个问题大小不对称，子问题太多，深度太深。一个可行的改进是，选三个元素，然后取中间的一个作为切分元素，这样效果会好些，但是仍然会有一些极端的情况会使得算法退化为平方。只要这三个元素是可以预计的，都能设计出让算法退化的输入。另一个改进方案是，选一个随机数。假设随机数发生器比较随机。但是只产生一个随机数，切分出来的效果还是不会很好，多产生几个随机数，再选中间数，效果会好些，只是产生随机数的过程本身就耗时，所以不能产生太多。

有些算法不用随机数，也能确保算法不会退化到平方。但是在实践中，这些算法速度很慢。

内观排序，即把快速排序跟堆排序结合起来。堆排序是很稳定的，不会退化，只是一般情况下比较慢。在快速排序t算法出现退化的情况下，再调用堆排序。问题是怎么判断退化。一种简单的方案是，当深度超过某值的时候，根据经验，这个值可以设为2*lgN。直接调用堆排序对切分后的子问题进行排序。

这个算法在平均情况下，跟快速排序差不多，在最坏情况下，比快速排序要快一个数量级。

介绍一下快速排序里在退化到n^2的情况下，怎样避免堆栈溢出。每次切分后，会产生两个子问题，对较小的子问题作递归，较大的子问题则替换掉原来的问题，然后继续循环，不用递归调用。这样虽然子问题还是很多，但是递归的深度却较小。