Recall that tail recursion optimization allows the compiler to reuse the current stack frame for the recursive call, effectively converting the recursion into iteration. How does this apply to quicksort's partitioning step?

Consider the worst-case scenario for quicksort where the pivot is always the smallest or largest element. How many recursive calls would be made in this case without tail recursion optimization? How does tail recursion optimization reduce this?

Implement a version of quicksort that uses tail recursion optimization for the larger partition. What is the maximum stack depth in this optimized version, and why is it guaranteed to be O(log n) in the average case?