General List Sorting Utilities MLG - 22 December 1981
------------------------------
The module Gsort (use LOAD GSORT) contains a number of general sorting
functions and associated key comparison functions. The Key comparison
functions are given 2 objects to compare, return NIL if they are not
in correct order:
BeforeFn(a:any,b:any):Extra-Boolean; % return NIL if not in order
The package defines:
NumberSortFn(N1:number,N2:Number)
StringSortFn(S1:String,N2:string) [Sc1 and Sc2 are faster versions]
IdSortFn(D1:id,D2:id) [IdC1 and IDc2 are faster]
AtomSortFn(X1:atom,X2:Atom)
The general sorting functions expect a SortFn (which MUST be an ID)
GsortP(Lst:x-list,BeforeFn:id):Boolean % T if x-list is sorted
Gsort(Lst:x-list,BeforeFn:id):x-list % Tree-sort of x-list
GMergeSort(Lst:x-list,BeforeFn:id):x-list % Merge-sort of x-list
Currently, Gsort is often fastest, but GMergeSort is more stable.
Example: To sort a list of Ids call Gsort(Dlist,'Idsortfn)
or Gsort(Dlist,'IDc2) for faster sort.
To sort list of records (e.g. pairs), user must define comparison:
E.g. to sort LP, a List of dotted pairs (Number . Info), define
procedure NPSortFn(P1,P2); NumberSortFn(Car p1, Car P2);
then execute Gsort(LP,'NPSortfn);
See PU:Gsort.Red for the code.