When does introsort go from quicksort to heapsort?

Question

Introsort starts with quick sorting and switches to heapsort when the recursion depth exceeds a level based on the number of elements sorted. What is this number? Is there a specific range or limit value?

Answer 1

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

depth_limit = 2 · ⎣log ₂ (l) ⎦

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

Answer 2

I just tried to read the introductory article on the Wikipedia article . It says:

It counts the depth of recursion. If the logarithmic depth is exceeded, the algorithm switches to Heapsort from Quicksort to save the worst case result Quicksort down

and through the original Musser paper on Introsort.

It says introsort is slower than heapsort because it executes 2 * log (2, N) before it switches to heapsort.

I understand that the recursion depth is 2 * log (2, N)

For N = 300 items to sort will be 2 * 8 = 16