1. Rewrite quicksort so that there are no recursive calls. The technique is to use a stack to keep track of which portions of the array still need to be sorted. Whenever we identify a portion of the...

1. Rewrite quicksort so that there are no recursive calls. The technique is to use a stack to keep track of which portions of the array still need to be sorted. Whenever we identify a portion of the array that still needs to be sorted, we will push two items onto the stack: (1) the starting index of the array segment and (2) the length of the array segment. The entire quicksort can now work as follows (with no recursion):

1. Push first and n onto the stack (indicating that we must sort the n-element array segment starting at data[first]).

2. while (the stack is not empty)

2a. Pop a size n and a starting index i off the stack. We must now sort the n-element array segment starting at data[i]. To do this sort, first use the assignment: pivotIndex = partition(data,i,n);

2b. If the area before the pivot index has more than one element, then we must sort this area. This area begins at data[i] and has pivotIndex-i elements, so push i and pivotIndex-i onto the stack.

2c. If the area after the pivot index has more than one element, then we must sort this area. Compute the starting point and length of this area in two local variables and push their values onto the stack.

With this approach, in the worst case the stack must be as big as the array that’s being sorted. This worst case occurs when we keep pushing two-element array segments onto the stack. However, there is a modification that reduces the maximum stack size. When you do steps 2b and 2c, make sure the larger array segment gets pushed onto the stack first. With this modification, the maximum necessary stack size is just 2 log₂
n. With this in mind, you can use a stack with a fixed size—for example, a 100-element stack is enough to sort an array with 2⁵⁰
elements.