When does introsort shift from quicksort to heapsort?

Question

Introsort begins with quicksort and switches to heapsort when the recursion depth exceeds a level based on the number of elements being sorted. What is that number? Is there a specific range or a limiting value?

Answer 1

The point at which the Introsort algorithm switches from Quicksort to Heapsort is determined by depth_limit:

depth_limit = 2 · ⎣log₂(l)⎦

Where l is the length of the sequence that is to be sorted, so l‍=‍n for the whole sequence. With each recursive call depth_limit is decremented by one. When depth_limit reaches 0, it switches from Quicksort to Heapsort.