Linked Lists
--------------

  type Node:
  	record
                info : string
  		next : ^Node
  	end record
  
  var top,bottom : ^Node
  

Merge 
--------

   % PreCond: aTop and bTop point at link lists SORTED by info field.
   % PostCond: nTop and nBottom return pointers to the merged list
   %    ie sorted. Common elements are added only once.
   %    lists aTop and bTop are unchanged.


eg 

  A          B       Merge
apple       cat      apple
banana      horse    banana
dog         man      cat
man         zoo      dog
woman                horse
                     man 
                     woman
                     zoo
   % Algorithm:
   % a and b will point at the next element in each list.
   % if they have different info fields, a copy of the smallest
   %     is inserted into the new list
   %     Then the next in A or B is obtained.
   % if they have the same in field, one copy is inserted and 
          next of both A and B is obtained.
   % if one list A or B is complete, copy the rest other list over.

    function merge (aTop, bTop : ^Node) : ^Node
        var a := aTop
        var b := bTop
        var top : ^Node
        new top % dummy record to make the code easier
        var bottom := top
        loop
            exit when a = nil and nextB = nil
            new bottom -> next
            bottom := bottom -> next
            if LT (a, b) then
                bottom -> info := a -> info
                a := a -> next
            elsif EQ (a, b)
                bottom -> info := a -> info 
                a := a -> next
                b := b -> next
            else % GT(a,b)
                bottom -> info := b -> info
                b := b -> next
            end if
        end loop
        var kill := top  % free dummy record
        top := top->next
        free kill
    end merge

  % Consider what happens when one of the list gets to the end 
  % but not the other, eg a=nil

    function LT (a, b : ^Node) : boolean
        if a = nil then
            result false
        elsif b = nil
            result true
        else
            result a -> info < b -> info
        end if
    end LT

    function EQ (a, b : ^Node) : boolean
        if a = nil and b = nil then
            result true
        elsif a = nil or b = nil
            result false
        else
            result a -> info = b -> info
        end if
    end EQ