{Begin SubSec Sorting Lists}
{Title Sorting Lists}
{Text

{note {fn SORT} was written by L. P. Deutsch.}

{FnDef {FnName SORT} {FnArgs DATA COMPAREFN}
{Text
{arg DATA} is a list of items to be sorted using {arg COMPAREFN}, a predicate
function of two arguments which can compare any two items on {arg DATA}
and return {lisp T}{Note T or non-NIL?} if the first one belongs before the second.
If {arg COMPAREFN} is {lisp NIL}, {fn ALPHORDER} is used; thus
{lisp (SORT {arg DATA})} will alphabetize a list.
If {arg COMPAREFN} is {lisp T}, {fn CAR}'s of items that are lists are given to {fn ALPHORDER}, otherwise the items themselves;
thus {lisp (SORT A-LIST T)} will alphabetize
an assoc list by the {fn CAR} of each item.
{lisp (SORT X 'ILESSP)} will sort a list of integers.

The value of {fn SORT} is the sorted list.
The sort is destructive and uses no extra storage.
The value returned is {fn EQ} to {arg DATA} but elements have been switched around.
Interrupting with control D, E, or B may cause loss of data, but control H may be used
at any time, and {fn SORT} will break at a clean state from which ↑ or control characters are safe.
The algorithm used by {fn SORT} is such that the maximum number of compares is {arg N}*log{sub 2}{arg N}, where {arg N} is {lisp (LENGTH {arg DATA})}.

Note: if {lisp ({arg COMPAREFN} A B)} = {lisp ({arg COMPAREFN} B A)}, then the ordering of {lisp A} and {lisp B} may or may not be preserved.

For example, if {lisp (FOO . FIE)} appears before {lisp (FOO . FUM)} in {lisp X}, {lisp (SORT X T)} may or may not reverse the order of these two elements.  Of course, the user can always specify a more precise {arg COMPAREFN}.
}}


{FnDef {FnName MERGE} {FnArgs A B COMPAREFN}
{Text
{arg A} and {arg B} are lists which have previously been sorted using
{fn SORT} and {arg COMPAREFN}.
Value is a destructive merging of the two lists.
It does not matter which list is longer.  After merging both {arg A} and {arg B} are equal to the merged list.
(In fact, {lisp (CDR {arg A})} is {fn EQ} to {lisp (CDR {arg B})}).
{fn MERGE} may be aborted after control-H.
}}


{FnDef {FnName ALPHORDER} {FnArgs A B CASEARRAY}
{Text
A predicate function of two arguments, for alphabetizing.  Returns a non-{lisp NIL} value if its arguments are in lexicographic order, i.e., if {arg B} does not belong before {arg A}.  Numbers come before literal atoms, and are ordered by magnitude (using {fn GREATERP}).  Literal atoms and strings are ordered by comparing the character codes in their print names.  Thus {lisp (ALPHORDER 23 123)} is {lisp T}, whereas {lisp (ALPHORDER 'A23 'A123)} is {lisp NIL}, because the character code for the digit 2 is greater than the code for 1.

Atoms and strings are ordered before all other data types.
If neither {arg A} nor {arg B} are atoms or strings, the
value of {fn ALPHORDER} is {lisp T}, i.e., in order.

If {arg CASEARRAY} is non-{lisp NIL}, it is a casearray ({PageRef Fn CASEARRAY} that the characters of {arg A} and {arg B} are translated through before being compared.  Note that numbers are not passed through {arg CASEARRAY}.

Note: If either {arg A} or {arg B} is a number, the value returned in the "true" case is {lisp T}.  Otherwise, {fn ALPHORDER} returns either {lisp EQUAL} or {lisp LESSP} to discriminate the cases of {arg A} and {arg B} being equal or unequal strings/atoms.

{note ALPHORDER should be changed to return LESSP and EQUAL for numbers, too --mjs}

Note: {fn ALPHORDER} does no {fn UNPACK}s, {fn CHCON}s, {fn CONS}es or {fn NTHCHAR}s.  It is several times faster for alphabetizing than anything that can be written using these other functions.
}}


{FnDef {Name UALPHORDER} {Args A B}
{Text
Defined as {lisp (ALPHORDER {arg A} {arg B} UPPERCASEARRAY)}.  {var UPPERCASEARRAY} ({PageRef Var UPPERCASEARRAY}) is a casearray that maps every lowercase character into the corresponding uppercase character.
}}


{FnDef {FnName MERGEINSERT} {FnArgs NEW LST ONEFLG}
{Text
{arg LST} is {lisp NIL} or a list of partially sorted items.
{fn MERGEINSERT} tries to find the "best" place to
(destructively) insert {arg NEW}, e.g.,

{lispcode
(MERGEINSERT 'FIE2 '(FOO FOO1 FIE FUM))
      =>   (FOO FOO1 FIE FIE2 FUM)}

Returns {arg LST}.  {fn MERGEINSERT} is undoable.

If {arg ONEFLG}={lisp T} and {arg NEW} is already a member of {arg LST}, {fn MERGEINSERT} does nothing and returns {arg LST}.
}}


{fn MERGEINSERT} is used by {fn ADDTOFILE} ({PageRef Fn ADDTOFILE}) to insert the name of a new function into a list of functions.  The algorithm is essentially to look for the item with the longest common leading sequence of characters with respect to {arg NEW}, and then merge {arg NEW} in starting at that point.


{FnDef {FnName COMPARELISTS} {FnArgs X Y}
{Text
Compares {arg X} and {arg Y} and prints their differences, i.e., {fn COMPARELISTS} is essentially a {index SRCCOM}{lisp SRCCOM} for list structures.{index comparing lists}

{Note Examples!!}
}}


}{End SubSec Sorting Lists}