Stack depth for QuickSort

CLRS Problem : 7.4

How does Tail-Recursive-QuickSort improve the efficiency of quick sort any better ?

Original quicksort

Tail recursive quicksort

Question

Modify the code for TAIL-RECURSIVE-QUICKSORT so that the worst-case stack depth is O(n log n). Maintain the O(n log n) expected running time of the algorithm.

We are always doing a tail-recursive call on the second partition. We can modify the algorithm to do the tail recursion on the larger partition. That way, we'll consume less stack.

Both algorithms sort the both partitions. But how does the stack consume less space by operating Tail-Recursive-QuickSort on larger partition?

• Welcome to Computer Science! Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! Jul 20, 2016 at 11:36
• Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! Jul 20, 2016 at 11:36
• I don't understand what your question is. Is that your answer or someone else's? What have you tried towards the analysis, and where did you get stuck? (Do you have a typo in the question? Vanilla Quicksort already has $O(n)$ worst-case stack depth; what we want is $O(\log n)$.) Jul 20, 2016 at 11:37
• So, why the expected depth is $O(\log N)$ if we choose a pivot randomly every call? Oct 7, 2017 at 17:23