algorithm - 什么时候 introsort 从快速排序转变为堆排序？

Question

Introsort从快速排序开始，当递归深度超过基于被排序元素数量的级别时切换到堆排序。那个数字是多少？有没有具体的范围或限值？

Answer 1

Introsort algorithm从 Quicksort 到 Heapsort 的切换由 depth_limit 决定:

depth_limit = 2 · ⎣log₂(l)⎦

其中l是待排序序列的长度，所以l‍=‍n为整个序列。随着每次递归调用，depth_limit 减一。当 depth_limit 达到 0 时，它从快速排序切换到堆排序。