Algorithm Analysis Question:The QUICKSORT algorithm of section 7.1 contains two recursive calls to itself. After the call to PARTITION, the left subarray is recursively sorted. The second recursive call in QUICKSORT is not really necessary:it can be avoided by using an iterative control structure. This technique, called tail recursion, is provided automatically by good compilers. Consider the following version of quicksort, which simulates tail recursion. QUICKSORT’ (A, p, r) while p
b) We managed to reduce the number of recursive calls by using tail-recursion but it can still use O(n) space in the worst case. How? If the array is sorted in decreasing order and last element is our pivot, then out left array will always have n-1 elements, making the stack go up to n. So this can be the scenario.
c) What if we just called recursion for the smaller part after the partition happens? If that is done, we can always have O(log n) as stack depth. Consider the code:
QuickSort(A, p, r)
while (p < r)
q = partition(A, p, r)
if (q – p < r – q) // if left part is smaller
quickSort(A, p, q – 1) //recursive call for left part
p = q + 1 //handle the right part
else //if right part is smaller
quickSort(A, q + 1, r) // recursive call for right part
r = q – 1 //handle the left part
This will ensure that recursion is always done on smaller part of the array i.e. reducing the size of the stack to almost half. The runtime is not affected as the same amount of work has to be done as before.
If you have any further doubts, let me know in the comments !