Introsort's depth counter and its small-partition cutoff

std::sort in most standard library implementations is introsort: quicksort augmented with a recursion-depth counter and a small-partition cutoff. If the recursion depth exceeds roughly 2·log2(n) without the partition finishing, the algorithm switches the remaining partition to heapsort; partitions smaller than a small constant (commonly 16) are finished with insertion sort instead of recursing further. Given that heapsort is Θ(n log n) worst case and insertion sort is Θ(n^2) worst case, what does each threshold actually guarantee or improve?

29 of 46 in Data Structures & Algorithms