Article 1643 of comp.sys.handhelds:
From: alonzo@microsoft.UUCP (Alonzo GARIEPY)
Newsgroups: comp.sys.handhelds
Subject: More quicksort
Date: 27 Mar 90 23:03:27 GMT
Organization: Microsoft Corp., Redmond WA

Here is yet another incarnation of quicksort for the HP 48.

This variation differs in that only one copy of each element
exists while the sort is taking place.  All objects are kept 
on the stack (as references) so that the memory overhead is 
about 5 nibbles per element (2500 bytes for a 1000 element
list).  This is most helpful when you are sorting large objects
or are low on memory.

It is possible to use less memory by sorting in place, but that
would be extremely slow because of list handling.  Sorting with 
an array of references is a typical way to avoid the cost of
copying data during a sort.

In one test, this sort took about 24 minutes for a list of 500 
random real number.  It could be made faster by eliminating one 
or both of the temporary variables.   The sort could be made
faster by replacing the code, 1 i START n ROLLD NEXT, with a
single machine code command.  I'll see what I can do.

QSORT
%%HP: T(3)A(D)F(.);
\<< LIST\-> QST \->LIST \>>	@ sorts a list on the stack @

QST
%%HP: T(3)A(D)F(.);
\<< \-> n			@ sorts a disassembled list on the stack @
    \<< n 2 / ROLL n 3 + 2 n
        START ROT 3 DUPN SWAP ROLLD > - NEXT 
	4 - \-> i 
	\<< n ROLLD 
            i IF DUP 1 > THEN QST END
            IF DUP THEN 1 SWAP START n ROLLD NEXT i END 
            n SWAP 1 + - IF DUP 1 > THEN QST END DROP n
\>> \>> \>>

Sedgewick has shown that by quicksorting only until no sublist contains
greater than X elements (where X is 10 to 20) and then doing an insertion
sort on the resultant almost-sorted list, it is possible to get up to 20%
improvement in speed.  Mark Adler brought this to my attention.  

You can do that by changing the two instances of "1 >" in QST to "X >".
Then you need to perform an insertion sort on the partly sorted result of
QSORT.  Since I haven't come up with a decent selection or insertion sort, 
I prefer to leave the resolution at 1 and take my lumps.  I invite others
to make these improvements.

The main speed considerations in sorting on the HP 28/48 are two.

1.  It is much faster to manipulate objects on the stack than to use 
    lists.  Moving stack objects is just a question of switching five 
    nibble pointers, but moving elements in a list involves copying
    the objects themselves with all the requisite memory managment.

2.  It is much faster to manipulate objects within global variables
    than those in the heap.  Each entry in the stack is a pointer to
    an object.  If the object was put on the stack by recalling or
    disassembling (GET, GETI, OBJ->, LIST->, etc.) a global variable,
    or by duplicating (DUP, OVER, etc.) an object that derives from
    a global variable, it will not be subject to garbage collection.
    Entries that result from calculation (PUT, ->LIST, +, SUB, etc.)
    point to objects in the heap and must be garbage collected.

The program above will sort a list of 500 random numbers in 4 minutes
and 21 seconds(1).  A list of 1000 random numbers took about 10 minutes
and 35 seconds(2).  If you want to make sure you get this behaviour for
lists on the stack that may not derive from global variables, you can 
modify QSORT to stash them in a temporary variable during the sort.

GQSORT
%%HP: T(3)A(D)F(.);
\<< 'QQQ' DUP PURGE STO QQQ LIST\-> QST 'QQQ' PURGE \->LIST \>>

Do not use GQSORT for big lists that are already in global variables
because storing a second copy in QQQ will make the sort slower.

Alonzo Gariepy
alonzo@microsoft

(1) On an HP 48 with 17 Kb of free memory (not including the list).
(2) On an HP 48 with 50 Kb of free memory (not including the list).