MARK SORT by Jeremy Hawdon, HPCC #600
Published in DATAFILE V9 N3, April/May 1990, p.22

This program sorts an array, list or stack of integers returning to level 1
a list sorted in descending order.  The type statements at the beginning of
the program turn a list or stack of numbers into a vector.  The array is
sorted in two passes into "range + 1" lists on the stack which are then
concatenated.

There is a speed advantage over other sorting programs when sorting a large
number of integers with a relatively small range of values.  For example in
sorting 100 integers with values from 0 to 20 sorting times were as follows:

         MSORT     18.4 s
         PSORT     49.7 s
         GSORT     74.6 s
         BSORT    362.2 s

PSORT is a numerical pigeon sort program, which sorts a list of n numbers
into n + 1 lists on the stack in a way quite similar to MSORT, then sorts
those lists recursively and recombines the sorted lists into a single list.

GSORT is the general purpose sort program from William C. Wickes' excellent
book "HP-28 Insights"; a version of the Quicksort algorithm.  The program
to time the sorts also came from this book.

BSORT is the Bubble Sort program by G. Miles (DATAFILE V7 N6) slightly
amended to accept and return a list.

-- Jeremy Hawdon
---------------------------------------------------------------------------
Additional notes by Joseph K. Horn:

Jeremy wrote this for the HP 28.  I changed the two LIST-> commands
to OBJ-> for the HP 48.  HP 28 fans can change them back if they wish.

Jeremy mentions that this program is fast when the data range is small; it
is unfortunate that when the data range is large, it really bogs down, and
requires a lot of memory, due to the way it creates "range + 1" lists on
the stack.  For example, the list {1 n n n 1 1 1 n n 1 n 1 1 1 n} with the
following values for n is sorted in this much time:

          n      time
          2      1.8 s
         10      2.0 s
        100      4.5 s
       1000     30.8 s
      10000    294.0 s  (4 min 54 sec)

When I tried to use n=100000, after a long time it ran out of memory
("Insufficient Memory" error), even though there was over 100K MEM at the
start.

Also, the program only sorts the integer part.  The list {2.3 2.2 3.2 3.3}
is "sorted" into {3.2 3.3 2.3 2.2}.  The fractional parts are ignored.

The moral is: use this program only when you only have integers (or don't
care about the fractional part), and when the data range is small.  -jkh-