I'm trying to learn about introsort and find resources to be scarce. My understanding is it uses quicksort, but switches to heapsort when the recurssion becomes to deep. This is because quicksort is generally faster than heapsort, unless the call depth becomes to deep.
My question is, how is the depth before switching to heapsort calculated? Wikipedia has floor(log(length_of_data))x2 but I've seen other things used. What is the reasoning? Am I correct the algorithm wants to stick with quicksort until it needs to switch to heapsort for memory reasons?
I've seen depth limits that range from ~ 1.5 * log2(n) to ~2.0 * log2(n). This is done to avoid worst case time complexity of O(n^2), not for space reasons.
Space complexity can be limited to O(log2(n)) by using a combination of a loop and recursion, only using recursion on the smaller "half" of each partition, then looping back to split the larger partition and continue the process. The loop back also decrements the depth counter, since it's being used to replace what would otherwise be another level of recursion.