UNIT mrgsort;
(* By C.B. Falconer, public domain. This is based on a description *)
(* in Sedgewicks 'Algorithms', but modified for isolation to a TP *)
(* unit, with a generalized linkage to the items to sort. *)

(* Since the 'info' field of a linknode is never used here, the *)
(* actual record may be designed as the application demands, so *)
(* long as the FIRST item in it is the 'next' pointer. Care must *)
(* then be taken not to modify the info field of 'null'. *)

(* The user defined 'greater' function will receive whatever type *)
(* of pointer is passed in to sort, and never the null pointer. *)

(* The list to be sorted must be terminated with a 'next' that *)
(* contains the value 'null', and it must be the null defined here. *)

INTERFACE

TYPE
greaterf = FUNCTION(thing, than : pointer) : boolean;

VAR
null : pointer; (* used as NIL substitute for end marks *)

FUNCTION sort(root : pointer; greater : greaterf) : pointer;
(* This provides a logical level for passing in the 'greater' proc. *)
(* note that these procedures do not use the header link, i.e. the *)
(* pointers they receive carry actual list data. The pointers will *)
(* later be defined as holding only the next and an 'info' pointer. *)
(* The info pointer will not be used here, so can be of any type. *)

IMPLEMENTATION
j