为什么introsort（内省排序）里用堆排序而不是希尔排序？

Question

introsort的大致思想是：当数据很大时先用quicksort，当递归超过一定深度时改用heapsort，最后每个子序列元素个数达到16时改用insertionsort
STL:sort 貌似也是introsort，希尔排序效率不是比堆排序好点吗，难道是处理大数据时的实际效率比不过堆排序？

Answer 1

quicksort，mergesort和heap sort都是最优和平均情况下都是O(nlogn)的算法， shell sort虽然最优是n（sorted），但是平均是O(nlog^2n)。在考虑实现时，大家考虑的平均情况，而不是最好的情况。