INSORT, Inserts an Object into an Already-Sorted List
by Joseph K. Horn

Differs from INSERT on Goodies Disk #8, which inserted any kind of
object into any kind of list at any desired location.  INSORT is
different; it figures out where to insert the object, assuming that
the list is already sorted.  It is intended for use by database-type
software, which keep lists sorted at all times.  No need to re-sort
the whole list; just use INSORT to add new items in the right place.

It can insert a number into a pre-sorted list of numbers, or a string
into a pre-sorted list of strings.

Inserting into a pre-sorted list can be done by a linear search, but
that's slow.  The following "binary search" method is much faster.  A
linear-search program takes 38 seconds to insert 888.8 into a list of
the integers 1 through 1000; this program takes less than two seconds,
most of which is spent merely executing the initial OBJ-> and the
final ->LIST.

Example:  { 5 7 9 11 13 }  10  INSORT
    -- >  { 5 7 9 10 11 13 }

Besides a normal insertion as illustrated above, three odd cases are
possible: (a) insertion of an item already in the list; (b) insertion
at either end of the list; and (c) insertion into an empty list.  This
program is able to handle all these cases.  Don't try to speed up the
routine by removing the tests for these cases, because there are no
such tests.  Just brilliant code.  ;-)

Note: All the items in the list must be comparable via the ">" test
with the new item being inserted.  An error will occur if any of the
object types don't allow the ">" test.  If the list is not already
sorted, the new item will be inserted without error, but at a
meaningless location.

Rewriting this in System RPL is left as an exercise for the reader.

-Joe Horn-

%%HP: T(3)A(D)F(.);
@ INSORT by Joe Horn; inserts into a pre-sorted list in the right place.
@ 2: List of pre-sorted reals or strings; 1: real or string.
\<<
  SWAP OBJ\-> DUP 2 + ROLL OVER 6 + 5
    WHILE DUP2 - 1 >
    REPEAT DUP2 + 2 / CEIL DUP PICK 5 PICK
      IF >
      THEN SWAP DROP
      ELSE ROT DROP SWAP
      END
    END DROP 4 -
  ROLLD 1 + \->LIST
\>>