MERGE SORT

Mergesort

The stack diagram of MERGE-SORT is ( list1 comparison-XT link-XT -- list2 )

A mergesort requires objects that have a link-field. During merging those link-fields are altered. list objects are tokens, possible an address, the first object representing the sublist of objects by following the links, finally arriving at a null pointer.

The list1 argument is a pointer to first object, thus representing the whole list. After sorting list1 may no longer be the first object, so mergesort returns list2 , a first object with respect the comparison.

A comparison-XT takes two list-objects and returns a flag, meaning the first object is smaller.

link-xt turns an object into its link-field, a cell where a token can be stored.

Example

We can compare two dictionary entry addresses in ciforth by

   \ For DEA1 and DEA2 return "dea1 IS lower".       
       : GET-NAME >NFA @ $@   ;  \ Aux. For DEA, return NAME.      
   : NAMES< SWAP >R GET-NAME    R> GET-NAME    COMPARE 0 < ;      
 

>LFA is a suitable word to serve as a link-xt

Now the dictionary can be sorted alphabetically by

   'FORTH >WID >LFA @   'NAMES< '>LFA MERGE-SORT   'FORTH >WID >LFA !

This illustrates a general trait of this sorting, the head of the list must be stored somewhere to be useful. Otherwise, in the example a part of the FORTH namespace would be locked out, and Forth would have become unusable.