## Introduction

This article was originally written in response to a discussion initiated by GurliGebis within the interesting article The ELMO Principle - Part 2 - Sorting Algorithms by UsualDosage. GurliGebis asked why Quicksort was not included to be tested. UsualDosage did not cover Quicksort, as he said that he was testing only non-recursive sorting algorithms. As I show here, there is no reason why Quicksort cannot be implemented iteratively and, indeed, such an implementation can show significant speed and memory-overhead advantages over a recursive implementation.

## Background

First off, I should say that I am not talking about the simple conversion of a recursive algorithm to an iterative implementation. Early versions of BASIC that some of us are unfortunately old enough to remember did not implement recursion and, as a consequence, if a recursive algorithm had to be implemented in these languages, then programmers would simply copy it and use explicit stack operations to mimic the recursive calls.

With Quicksort, although this can of course be done (any recursive algorithm can be converted to an iterative equivalent; whether it's a good idea or not is another matter!), it turns out that there are significant advantages in terms of both memory utilisation and, for typical input data, speed, if a modified iterative implementation is provided that does not have a direct recursive equivalent.

The advantages of using an explicit stack and iteration in place of a recursive implementation are essentially three-fold:

- Using an explicit stack allows the sort to avoid the temporary storage of unnecessary information.
- Rather than placing two partitions on a stack in arbitrary order, as a typical recursive Quicksort would implicitly do, the sizes of the partitions are checked first and the pointers indicating the larger of the two are stacked. The smaller partition's pointers are not stacked at all: we are able to do this since we can guarantee that the smaller partition would always be equivalent to the second recursive call, which is at the tail-end of the function. This leads to the third advantage:
- Any tail-end recursion can be eliminated and replaced with a simple loop.

This combination of ensuring end-recursion removal and always processing the smaller of the two partitions ensures that the stack only has to contain a maximum of **O(log(n))** entries, hence the potential memory savings mentioned earlier. Note that in the worst case (in which, for example, the input data is already sorted), the stack-size for a recursive implementation would grow to be as large as the number of records in the array.

## Using the Code

The program is extremely simple to operate. Simply press the "Generate New Data" button and then "Do Sort!" Use the numeric up/down box to set the maximum number of integers to be randomly generated by pressing the generate button. The "Do Sort!" button is only enabled when a change to the input data has been completed. The radio option buttons allow the user to select whether they wish the data to be sorted in ascending or descending order.

## Code

Here is the sorting function from the `IttvQuickSort`

class that actually does the work. Note that when timing, it's typically best to ignore the first run. Sorting a million integers takes an average of around half a second on my machine: AMD Sempron 2600+, 1GB memory, Windows XP SP2. Any variation is, of course, due to the order in which the input data is presented to the sort, as well as any other processes that may be calling for the processor's attention.

private bool ExecuteActualSort(int nFirst, int nLast, bool bAscend)
{
bool bSortOK = false;
try
{
int i, j, nStkPtr = 0, nTmp;
bool bSortCompleted = false, bDirection = true;
int nStackMax = (int)((Math.Log(nLast) + 3) * 2);
int[,] nStack = new int[nStackMax, 2];
do
{
do
{
i = nFirst;
j = nLast;
bDirection = true;
do
{
if ((nData[i] > nData[j]) == bAscend)
{
nTmp = nData[i];
nData[i] = nData[j];
nData[j] = nTmp;
bDirection = !bDirection;
}
if (bDirection)
j--;
else
i++;
}
while (i < j);
if (i + 1 < nLast)
{
nStkPtr++;
nStack[nStkPtr, 0] = i + 1;
nStack[nStkPtr, 1] = nLast;
}
nLast = i - 1;
}
while (nFirst < nLast);
if (nStkPtr == 0)
{
bSortCompleted = true;
}
else
{
nFirst = nStack[nStkPtr, 0];
nLast = nStack[nStkPtr, 1];
nStkPtr--;
}
}
while (!bSortCompleted);
bSortOK = true;
}
catch { }
return bSortOK;
}

This is a C# conversion of an iterative Quicksort that I wrote in BBC BASIC around 1988 that ran on an ARM2-based machine. However, it should be mentioned that BBC BASIC was highly advanced for its time and, ironically, given the subject matter of this article, most certainly did support recursion!

## History

- 25 January, 2008 -- First version

## References

- Knuth (1998) (2nd Ed), The Art of Computer Programming Vol. 3 pp115-123. Addison-Wesley.
- Sedgewick (1983), Algorithms pp103-113. Addison-Wesley.
- Quillinan (1985), Better BASIC pp98. Newnes. (For an example of a straight conversion without the advantages)