{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}
{Text
A predicate function of two arguments, for alphabetizing.
Returns {lisp T} if its arguments are in 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 pnames.
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.

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 {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.,

{lisp (MERGEINSERT 'FIE2 '(FOO FOO1 FIE FUM))} = {lisp (FOO FOO1 FIE FIE2 FUM)}.

Value is {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.

{Note Examples!!}
}}


}{End SubSec Sorting Lists}