Problem 7-4

Stack depth for quicksort

The \(\textsc{Quicksort}\) algorithm of Section 7.1 contains two recursive calls to itself. After \(\textsc{Quicksort}\) calls \(\textsc{Partition}\), it recursively sorts the left subarray and then it recursively sorts the right subarray. The second recursive call in \(\textsc{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:

$$\textsc{Tail-Recursive-Quicksort}(A, p, r)$$$$\begin{aligned} 1& \quad \textbf{while }\,p\,<\,r \\ 2& \quad \qquad \textbf{/\!/} \text{ Partition}\,\text{ and}\,\text{ sort}\,\text{ left}\,\text{ subarray.}\, \\ 3& \quad \qquad q\,=\,\textsc{Partition}(A, \, p, \, r) \\ 4& \quad \qquad \textsc{Tail-Recursive-Quicksort}(A, \, p, \, q - 1) \\ 5& \quad \qquad p\,=\,q\,+\,1 \\ \end{aligned}$$

1. Argue that \(\textsc{Tail-Recursive-Quicksort}(A, 1, A.length)\) correctly sorts the array \(A\).

2. 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.

   Describe a scenario in which \(\textsc{Tail-Recursive-Quicksort}\)’s stack depth is \(\Theta(n)\) on an \(n\)-element input array.

3. Modify the code for \(\textsc{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.

Tail recursion elimination is a classic optimization that can significantly reduce stack space usage in recursive algorithms. For quicksort, we can do even better by making smart choices about which subarray to recurse on first.

A.

The tail-recursive version is equivalent to the original quicksort. Let’s trace through the logic:

1. The while loop continues as long as the current subarray \(A[p..r]\) has at least two elements
2. \(\textsc{Partition}\) rearranges \(A[p..r]\) so that \(A[p..q-1] \leq A[q] \leq A[q+1..r]\)
3. The recursive call sorts the left subarray \(A[p..q-1]\)
4. Setting \(p = q+1\) prepares to sort the right subarray in the next iteration

After the recursive call in step 3, the left subarray is sorted. The while loop then continues with the right subarray \(A[q+1..r]\). This process continues until all subarrays are sorted.

The algorithm is correct because:

• Every partition operation maintains the invariant that elements are properly arranged around the pivot
• The left subarray is sorted recursively
• The right subarray is sorted iteratively (via the while loop)
• When the while loop terminates, all subarrays of size 1 or empty remain, meaning the entire array is sorted

B.

The worst-case stack depth occurs when we consistently partition unbalanced subarrays and always recurse on the larger side. Consider an array already sorted in increasing order: \(A = \langle 1, 2, 3, \ldots, n \rangle\).

With the last element as pivot:

• First partition: pivot is \(n\), largest element. Left subarray has \(n-1\) elements, right subarray is empty
• We recursively sort \(A[1..n-1]\), which leads to another unbalanced partition
• Second partition: pivot is \(n-1\), largest remaining element. Left subarray has \(n-2\) elements
• This pattern continues…

Each recursive call handles a subarray of size \(n-1, n-2, n-3, \ldots, 1\). Since the recursion goes to the left subarray every time, and the right subarray is handled iteratively, we build up a call stack of depth:

This happens because we recurse on the large side (\(n-1\) elements) and iterate on the small side (0 elements), leading to a deep recursion tree along one branch.

C.

The key insight is to always recurse on the smaller subarray and iterate on the larger one, which ensures the recursion depth is logarithmic.

To analyze the stack depth, let \(D(n)\) be the maximum stack depth on an array of size \(n\).

When we partition an array of size \(n\) into subarrays of sizes \(k\) and \(n-k-1\):

• We recurse on the smaller subarray (size at most \(\lfloor n/2 \rfloor\))
• We iterate on the larger subarray

The recurrence for stack depth is:

This is because each recursive call reduces the problem size by at least half. Solving this recurrence:

In the worst case, we make \(\lg n\) recursive calls before reaching subarrays of size 1.

The modification doesn’t affect the asymptotic running time. We still perform the same partitions and comparisons; we’ve only changed the order in which subarrays are processed. The expected running time remains:

The key improvement is that we’ve reduced worst-case stack space from \(\Theta(n)\) to \(\Theta(\lg n)\) without any asymptotic time penalty.