Tail Call Is Not Enough

This quicksort replaces the second recursive call with a loop, the standard tail-call elimination:

void qsort_tail(int a[], int p, int r) {
    while (p < r) {
        int q = partition(a, p, r);
        qsort_tail(a, p, q - 1);
        p = q + 1;
    }
}

What is its worst case stack depth, and what change bounds it at $O(\log n)$ ?

$\Theta(n)$ , and there is no fix short of an explicit stack, since quicksort's recursion depth is inherently linear in the worst case.

$\Theta(n)$ . On an already-sorted array partition returns q = r every time, so the recursive call always receives the large side. Compare the two side lengths and recurse into the shorter one, iterating on the longer.

$\Theta(\log n)$ already. Removing one of the two calls is what bounds the depth.

$\Theta(n)$ , and the fix is median-of-three pivot selection.