From: jhmeyers@miu.edu (John H Meyers)
Subject: How SORT works (plus S/SX version)
Date: 19 Mar 1998 00:00:00 GMT
Message-ID: <6eqpqv$1k3$2@news.iastate.edu>
Reply-To: jhmeyers@miu.edu
Organization: MIU Computer Services,  Fairfield, IA 52557.  Not Approved.
Newsgroups: comp.sys.hp48


On 1997/12/31, Mike McGranahan <tmcgrana@ix.netcom.com>
(class of 1998, south hills high school) inquired:

> What sorting method does the SORT command employ?
> --and/or--
> By what means can I disassemble a command in the HP ROM?
> (i.e. how can I view the source for a command like SORT)

  "Jazz" <http://www.hut.fi/~mheiskan> answers the second question;
  e.g. disassemble { SORT } and use ED to further disassemble
  ROMPTR E8 16, which does most of the work.  Within this
  subprogram, the loop which does the sorting looks very much like
  Joe Horn's SysRPL programs SORTLN and SORTLS (Goodies Disk #8),
  which should still work in all HP48 versions to date.

  These programs, in turn, take the approach that if we have some items
  which have already been sorted, then we can insert one more item into
  its proper place by performing a "binary search" among the already-
  sorted items; this means that we look at the "middle item" of the
  sorted list, and then decide in which half of the list our new item
  belongs, repeating until the narrowed-down list contains just two items,
  between which we insert our new item.  To sort a whole list, we start
  with an empty list of "already sorted" items, inserting one new item
  at a time from the original unsorted list, until all items have been
  inserted into their proper final places in the result list.

  Knuth downplays this "sorting by [binary] insertion" method in his
  "Sorting and Searching" text, because of the fact that in most
  computers, the "insertion" operation takes enough time to nullify
  the advantage gained by making so few comparisons; however, in the
  HP48, the "insertion" is performed by an UNROLL (ROLLD) of the stack,
  which is an efficient ML routine -- certainly more efficient
  than any non-ML routine for swapping items, as required by other
  methods of sorting.  Knuth also notes that this very method was
  mentioned by computer pioneer John Mauchly in 1946, in the first
  published discussion of computer sorting.  It is also handy for
  hand-sorting of index cards, etc., because of the fact that the
  insertion operation takes virtually no time at all in such cases :)

  The procedure used in the binary search alone can be examined using
  Joe Horn's User-RPL program INSORT (Goodies Disk #10 / PR); you give
  that program an already-sorted list, plus one new item to be inserted,
  and it returns to you the resulting list, after inserting the new item.

  To account for a possible insertion before the first or after the
  last current list item, the initial "pointers" into the list
  (which is actually split into individual stack levels during all of
  the above programs) are actually set to point to non-existent items
  before the first and after the last "real" current item; the binary
  search loop looks for a "middle item" only so long as these pointers
  differ by at least two items, which ensures that a real "middle item"
  always exists, until the pointers differ by exactly 1 item, which
  indicates that the new item should be inserted between these.

  You can sort any list, as above, by using the following additional
  program along with INSORT:  \<< { } SWAP 1 'INSORT' DOSUBS \>>

  What this little program does is to start with an empty list,
  then insert each individual item from the original unsorted list.

  Of course, it is inefficient to keep using the whole of INSORT
  for every item, because INSORT always starts with OBJ->
  (to break up the list into individual stack levels)
  and ends with ->LIST (to re-build the list); it is more efficient
  to break up the list just once (when sorting begins) and re-build it
  just once (when sorting is finished), which is what all the other
  programs (SORTLN, SORTLS, and the internal SORT) actually do.

  The following minor modification to INSORT allows it to work as well
  with a list of variable names (e.g. from VARS):

\<< @ { sorted list } new_item  ==>  { augmented sorted list }
  SWAP LIST\-> DUP 2 + ROLL OVER 6 + 5 @ Changed OBJ\-> to LIST\->
    WHILE DUP2 - 1 >
    REPEAT DUP2 + 2 / CEIL DUP PICK 5 PICK
    OVER TYPE OVER TYPE + { \->STR SWAP \->STR SWAP } IFT @ Newly added
      > @ Changed to use IFTE
      { SWAP DROP }
      { ROT DROP SWAP }
      IFTE
    END DROP 4 -
  ROLLD 1 + \->LIST
\>>

The use of ->STR to convert all non-numeric objects to strings has
a rare flaw when used with names, e.g. '$' should come before '$$',
but "'$$'" comes before "'$'" (because "$" is less than "'" in ascii);
binary or unit objects, etc., are also not sortable by the above.

The built-in G/GX SORT is much more intelligent when comparing items;
for example, it correctly sorts { { 11 A } { 1 B } { 5 C } } by the
numeric values of the initial elements in the set of lists to be sorted
(even if these elements are "nested" even more deeply into sublists);
the "compare" part of the internal SORT is embedded in a very sneaky
manner at the end of the function, using a couple of absolute offsets
which depend upon the exact length of some of the compiled sections
of the code, so watch out if you attempt to alter the DIS'd code.

If one desires to make a somewhat generalized single SORT command for
the HP48S/SX, but not quite as complete as the G/GX internal version,
one might take either SORTLN or SORTLS and modify it,
somewhat as INSORT was modified above, e.g.:

:: CK1&Dispatch FIVE
  :: INNERCOMP 1LAMBIND 1GETLAM
    #1+_ONE_DO 1GETLAM ROLL ZERO INDEX@
      BEGIN ?ATTNQUIT 2DUP SWAP#- #2/ DUP#0<>
      WHILE
        :: OVERSWAP #-DUP #4+PICK 5PICK
          :: CK&DISPATCH1 ( Added for various object types )
            SEVENTEEN :: %> COERCEFLAG ; ( real )
            FIFTYONE PTR 1420A ( string )
            #66 :: ID>$ SWAP ID>$ SWAP PTR 1420A ; ( ID )
            ZERO :: PTR 18F6A x> ; ( EvalNoCK: everything else )
            ( Binary and unit objects compare as would be expected. )
            ( Some invalid object types & combinations go undetected, )
            ( in which case the result is harmless but meaningless. )
            ( Note that inner lists are not accepted. )
          ;
          %0<> ITE ROTDROPSWAP SWAPDROP
        ;
      REPEAT ROT2DROP UNROLL
    LOOP 1GETABND {}N
  ;
;

The resemblance between Joe Horn's program and the actual G/GX library
function is so great that it looks as if HP stole it directly from Joe :)

Here is the above in ASC format (see the FAQ for how to use it);
as always, one should make backups before trying out randomly posted
SysRPL programs, especially any that are posted by me :)

%%HP: T(3);
"D9D20ECE8112040D9D20FA450FC4366B316BD3706B31652330FEF30122702A17
0E3424CA13049726E8E304D226EE170D9D2013D268F7261E116A3216D9D202BF
8199040D9D20A88A2E0835B213085B46A02411192066000D9D209EB50322309E
B5032230A0241B2130FEF30D9D20A6F81D5CE1B2130B2130FC7A28DA16E0F06B
9F06B21305E17062726E9330433706B43695450B2130B21306019"

There also exist other efficient methods for sorting certain classes
of objects; for example, see SORTR (GD#10/PR) for case-insensitive
string sorting, MSORT (GD#1) for integer sorting, QSDIR (GD#2) and
QSHORT (GD#11/PR) for  "Quicksort" algorithms, and QSORT (GD#11/PR)
for sorting a numeric array.  I thought I once spotted a "heap" sort
program somewhere, but I can't find it today.

Anyone remember Honeywell's "Read-Backwards PolyPhase Tape Sort" ?
(Don't try this on your Turing Machine at home :)

-----------------------------------------------------------
With best wishes from:   John H Meyers   <jhmeyers@mum.edu>
