7-4 Stack depth for quicksort

The $\text{QUICKSORT}$ algorithm of Section 7.1 contains two recursive calls to itself. After $\text{QUICKSORT}$ calls $\text{PARTITION}$, it recursively sorts the left subarray and then it recursively sorts the right subarray. The second recursive call in $\text{QUICKSORT}$ is not really necessary; we can avoid it 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:

1
2
3
4
5
6
TAIL-RECURSIVE-QUICKSORT(A, p, r)
    while p < r
        // Partition and sort left subarray.
        q = PARTITION(A, p, r)
        TAIL-RECURSIVE-QUICKSORT(A, p, q - 1)
        p = q + 1

a. Argue that $\text{TAIL-RECURSIVE-QUICKSORT}(A, 1, A.length)$ correctly sorts the array $A$.

Compilers usually execute recursive procedures by using a stack that contains pertinent information, including the parameter values, for each recursive call. The information for the most recent call is at the top of the stack, and the information for the initial call is at the bottom. Upon calling a procedure, its information is pushed onto the stack; when it terminates, its information is popped. Since we assume that array parameters are represented by pointers, the information for each procedure call on the stack requires $O(1)$ stack space. The stack depth is the maximum amount of stack space used at any time during a computation.

b. Describe a scenario in which $\text{TAIL-RECURSIVE-QUICKSORT}$'s stack depth is $\Theta(n)$ on an $n$-element input array.

c. Modify the code for $\text{TAIL-RECURSIVE-QUICKSORT}$ so that the worst-case stack depth is $\Theta(\lg n)$. Maintain the $O(n\lg n)$ expected running time of the algorithm.

a. $\text{QUICKSORT}'$ does exactly what $\text{QUICKSORT}$ does; hence it sorts correctly.

$\text{QUICKSORT}$ and $\text{QUICKSORT}'$ do the same partitioning, and then each calls itself with arguments $A$, $p$, $q - 1$. $\text{QUICKSORT}$ then calls itself again, with arguments $A$, $q + 1$, $r$. $\text{QUICKSORT}'$ instead sets $p = q + 1$ and performs another iteration of its while loop. This executes the same operations as calling itself with $A$, $q + 1$, $r$, because in both cases, the first and third arguments ($A$ and $r$) have the same values as before, and $p$ has the old value of $q + 1$.

b. The stack depth of $\text{QUICKSORT}'$ will be $\Theta(n)$ on an $n$-element input array if there are $\Theta(n)$ recursive calls to $\text{QUICKSORT}'$. This happens if every call to $\text{PARTITION}(A, p, r)$ returns $q = r$. The sequence of recursive calls in this scenario is

$$ \begin{aligned} & \text{QUICKSORT$'(A, 1, n)$}, \\ & \text{QUICKSORT$'(A, 1, n - 1)$}, \\ & \text{QUICKSORT$'(A, 1, n - 2)$}, \\ & \quad\quad\vdots \\ & \text{QUICKSORT$'(A, 1, 1)$}. \end{aligned} $$

Any array that is already sorted in increasing order will cause $\text{QUICKSORT}'$ to behave this way.

c. The problem demonstrated by the scenario in part (b) is that each invocation of $\text{QUICKSORT}'$ calls $\text{QUICKSORT}'$ again with almost the same range. To avoid such behavior, we must change $\text{QUICKSORT}'$ so that the recursive call is on a smaller interval of the array. The following variation of $\text{QUICKSORT}'$ checks which of the two subarrays returned from $\text{PARTITION}$ is smaller and recurses on the smaller subarray, which is at most half the size of the current array. Since the array size is reduced by at least half on each recursive call, the number of recursive calls, and hence the stack depth, is $\Theta(\lg n)$ in the worst case. Note that this method works no matter how partitioning is performed (as long as the $\text{PARTITION}$ procedure has the same functionality as the procedure given in Section 7.1).

1
2
3
4
5
6
7
8
9
QUICKSORT''(A, p, r)
    while p < r
        // Partition and sort the small subarray first.
        q = PARTITION(A, p, r)
        if q - p < r - q
            QUICKSORT''(A, p, q - 1)
            p = q + 1
        else QUICKSORT''(A, q + 1, r)
            r = q - 1

The expected running time is not affected, because exactly the same work is done as before: the same partitions are produced, and the same subarrays are sorted.