The procedure quicksort may now be written, recursively, as follows.
Recursive Version
To sort a global array of n records, quicksort(1,n) is invoked. The crux of the algorithm is the partition function, which will be discussed shortly.
Every time a call is made to quicksort, two new obligations are incurred, and a current obligation is postponed. For instance, the initial call to quicksort generates the initial obligation: sort the n entries of data. During the execution of this call, partition determines a partitioning entry, and two new obligations are incurred. These are represented by the two recursive calls to quicksort, one for each component. The current obligation must then be postponed to carry out these new obligations. Each recursive call also generates two new obligations, requiring the execution of the current recursive call to be postponed.
As we have seen previously, what can be done recursively can also be done iteratively. Quicksort can be written nonrecursively by using a stack to store one of the new obligations, while the other can be processed immediately. It turns out that the choice of which of the two obligations to stack, and which to deal with immediately, is critical to the algorithm's storage requirements. The partition function does not necessarily split an array into two equal parts, as evidenced by our earlier example. Selecting the larger of the two components to stack results in a worst-case stack depth of O (lg n). An arbitrary choice instead leads to a worst-case stack depth of O (n). The difference in storage needed for the stack can be significant.quicksort(i,j)
/* Sorts the records stored in array data
between positions indexed by i and j in
descending order.
*/
int i,j;
{int p;
if(i < j)
{p = partition(i,j);
quicksort(i,p-1);
quicksort(p+1,j);
}
}