Ok Ted, here's Ethan Winer's version of Quicksort

BASIC TECHNIQUES AND UTILITIES BOOK
By Ethan Winer
Chapter 8 Sorting and Searching
Extract only of Quick Sort Algorithm (without recursion)

THE QUICK SORT ALGORITHM
========================
It should be obvious to you by now that a routine written in assembly
language will always be faster than an equivalent written in BASIC.
However, simply translating a procedure to assembly language is not always
the best solution. Far more important than which language you use is
selecting an appropriate algorithm. The best sorting method I know is the
Quick Sort, and a well-written version of Quick Sort using BASIC will be
many times faster than an assembly language implementation of the Bubble
Sort.
The main problem with the Bubble Sort is that the number of comparisons
required grows exponentially as the number of elements increases. Since
each pass through the array exchanges only a few elements, many passes are
required before the entire array is sorted. The Quick Sort was developed
by C.A.R. (Tony) Hoare, and is widely recognized as the fastest algorithm
available. In some special cases, such as when the data is already sorted
or nearly sorted, the Quick Sort may be slightly slower than other methods.
But in most situations, a Quick Sort is many times faster than any other
sorting algorithm.
As with the Bubble Sort, there are many different variations on how a
Quick Sort may be coded. (You may have noticed that the Bubble Sort shown
in Chapter 7 used a nested FOR/NEXT loop, while the one shown here uses a
FOR/NEXT loop within a DO/WHILE loop.) A Quick Sort divides the array into
sections--sometimes called partitions--and then sorts each section
individually. Many implementations therefore use recursion to invoke the
subprogram from within itself, as each new section is about to be sorted.
However, recursive procedures in any language are notoriously slow, and
also consume stack memory at an alarming rate.
The Quick Sort version presented here avoids recursion, and instead uses
a local array as a form of stack. This array stores the upper and lower
bounds showing which section of the array is currently being considered.
Another refinement I have added is to avoid making a copy of elements in
the array. As a Quick Sort progresses, it examines one element selected
arbitrarily from the middle of the array, and compares it to the elements
that lie above and below it. To avoid assigning a temporary copy this
version simply keeps track of the selected element number.
When sorting numeric data, maintaining a copy of the element is
reasonable. But when sorting strings--especially strings whose length is
not known ahead of time--the time and memory required to keep a copy can
become problematic. For clarity, the generic Quick Sort shown below uses
the copy method. Although this version is meant for sorting a single
precision array, it can easily be adapted to sort any type of data by
simply changing all instances of the "!" type declaration character.

'******** QSORT.BAS, Quick Sort algorithm demonstration

'Copyright (c) 1991 Ethan Winer

DEFINT A-Z
DECLARE SUB QSort (Array!(), StartEl, NumEls)

RANDOMIZE TIMER 'generate a new series each run

DIM Array!(1 TO 21) 'create an array
FOR X = 1 TO 21 'fill with random numbers
Array!(X) = RND(1) * 500 'between 0 and 500
NEXT

FirstEl = 6 'sort starting here
NumEls = 10 'sort this many elements

CLS
PRINT "Before Sorting:"; TAB(31); "After sorting:"
PRINT "==============="; TAB(31); "=============="

FOR X = 1 TO 21 'show them before sorting
IF X >= FirstEl AND X <= FirstEl + NumEls - 1 THEN
PRINT "==>";
END IF
PRINT TAB(5); USING "###.##"; Array!(X)
NEXT

CALL QSort(Array!(), FirstEl, NumEls)

LOCATE 3
FOR X = 1 TO 21 'print them after sorting
LOCATE , 30
IF X >= FirstEl AND X <= FirstEl + NumEls - 1 THEN
PRINT "==>"; 'point to sorted items
END IF
LOCATE , 35
PRINT USING "###.##"; Array!(X)
NEXT

SUB QSort (Array!(), StartEl, NumEls) STATIC

REDIM QStack(NumEls \ 5 + 10) 'create a stack array

First = StartEl 'initialize work variables
Last = StartEl + NumEls - 1
StackPtr = 0 'added 10/31/2005 - thanks to Edward F. Moneo

DO
DO
Temp! = Array!((Last + First) \ 2) 'seek midpoint
I = First
J = Last

DO 'reverse both < and > below to sort descending
WHILE Array!(I) < Temp!
I = I + 1
WEND
WHILE Array!(J) > Temp!
J = J - 1
WEND
IF I > J THEN EXIT DO
IF I < J THEN SWAP Array!(I), Array!(J)
I = I + 1
J = J - 1
LOOP WHILE I <= J

IF I < Last THEN
QStack(StackPtr) = I 'Push I
QStack(StackPtr + 1) = Last 'Push Last
StackPtr = StackPtr + 2
END IF

Last = J
LOOP WHILE First < Last

IF StackPtr = 0 THEN EXIT DO 'Done
StackPtr = StackPtr - 2
First = QStack(StackPtr) 'Pop First
Last = QStack(StackPtr + 1) 'Pop Last
LOOP

ERASE QStack 'delete the stack array

END SUB

Notice that I have designed this routine to allow sorting only a portion
of the array. To sort the entire array you'd simply omit the StartEl and
NumEls parameters, and assign First and Last from the LBOUND and UBOUND
element numbers. That is, you will change these:

First = StartEl
and
Last = StartEl + NumEls - 1

to these:

First = LBOUND(Array!)
and
Last = UBOUND(Array!)

As I mentioned earlier, the QStack array serves as a table of element
numbers that reflect which range of elements is currently being considered.
You will need to dimension this array to one element for every five
elements in the primary array being sorted, plus a few extra for good
measure. In this program I added ten elements, because one stack element
for every five main array elements is not enough for very small arrays.
For data arrays that have a large amount of duplicated items, you will
probably need to increase the size of the stack array.
Note that this ratio is not an absolute--the exact size of the stack
that is needed depends on how badly out of order the data is to begin with.
Although it is possible that one stack element for every five in the main
array is insufficient in a given situation, I have never seen this formula
fail. Because the stack is a dynamic integer array that is stored in far
memory, it will not impinge on near string memory. If this routine were
designed using the normal recursive method, BASIC's stack would be used
which is in near memory.
Each of the innermost DO loops searches the array for the first element
in each section about the midpoint that belongs in the other section. If
the elements are indeed out of order (when I is less than J) the elements
are exchanged. This incrementing and comparing continues until I and J
cross. At that point, assuming the variable I has not exceeded the upper
limits of the current partition, the partition bounds are saved and Last
is assigned to the top of the next inner partition level. When the entire
partition has been processed, the previous bounds are retrieved, but as a
new set of First and Last values. This process continues until no more
partition boundaries are on the stack. At that point the entire array is
sorted.
On the accompanying disk you will find a program called SEEQSORT.BAS
that contains an enhanced version of the QSort demo and subprogram. This
program lets you watch the progress of the comparisons and exchanges as
they are made, and actually see this complex algorithm operate. Simply
load SEEQSORT.BAS into the BASIC editor and run it. A constant named
Delay! is defined at the beginning of the program. Increasing its value
makes the program run more slowly; decreasing it causes the program to run
faster.

*****