CLRS Problem : 7.4
Tail-Recursive-QuickSort improve the efficiency of quick sort any better ?
Tail recursive quicksort
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?