Initially, the stack is empty, and the array is as shown in Figure 8.18(a). When quicksort (1,8) is invoked, it calls partition (1,8), which returns with p pointing to the partitioning entry and the rearranged array of Figure 8.18(b).
The upper component array is the larger, so (1,4) is placed on the stack, and the lower component array is processed. This leads to a call to partition (6,8). When partition returns, the situation is Figure 8.18(c).
Figure 8.18 Iterative Quicksort
The current upper component array is larger, so (6,7) is placed on the stack, and the lower component array is processed. Since the lower component contains no entries, (6,7) is removed from the stack and partition(6,7) is invoked, returning the situation depicted in Figure 8.18(d).
Now (6,6) is placed on the stack, and the lower component is processed. Again, this component has no entries, so (6,6) is removed from the stack. Since top (= 6) is not less than bottom (= 6), the outer while loop body is now executed, causing (1,4) to be removed from the stack. At this time the stack is empty, and the array is as shown in Figure 8.18(e). Partition(1,4) is now invoked, and returns, yielding Figure 8.18(f).
Now (1,3) is placed on the stack. The lower component again contains no entries, so (1,3) is removed from the stack, and partition(1,3) is invoked. The result is Figure 8.18(g).
At this point (2,3) is placed on the stack. Since the upper component contains no entries, (2,3) is removed from the stack, and partition(2,3) is invoked. It returns with Figure 8.18(h).
Now (2,2) is placed on the stack. The lower component has no entries, so (2,2) is removed from the stack. Since top (= 2) and bottom (= 2), the outer while loop tests for an empty stack. As the stack is empty, quicksort terminates.
It should not be clear that each time the inner loop body of quicksort is executed, and top < bottom, p is set to point to an entry of the array that has been correctly placed in its final sorted position. If top = bottom, then the one entry is already in its proper sorted position. The inner loop body is thus executed at most n times. Ignoring the time taken by partition, the inner loop body takes a constant time to execute. Each time the inner loop body executes, it generates one new problem that is placed on the stack and another new problem that is processed immediately. As soon as this latter problem has fewer than two entries (top ?/FONT> bottom), the inner loop is exited. Unless the stack is empty, the outer loop removes the next problem from the stack, and the inner loop then functions again. Consequently, each entry that is placed in its proper position requires, at most, an execution of the inner loop body or an execution of the inner loop body plus the additional constant time required by the outer loop test plus removal of a problem from the stack. This means that the total time is, at most, c1 + c2 x n plus the total time taken by partition, for some constants c1 and c2.