program mergeTest (input, output);

type
    ElementPtrType = ^ElementType;
    ElementType = record
		      data: integer;
		      next: ElementPtrType;
		  end;

var
    list1, list2, list3: ElementPtrType;

#include "listutils.i";

{
    Copy the smaller of the heads of the two nonnull lists listSource1
    and listSource2 into a node pointed to by DestElement.
    Then move the appropriate source pointer up.
}
procedure CopySmallerAndMoveUp (var destElement,
			        listSource1, listSource2: ElementPtrType);
begin
    assert (listSource1 <> nil);
    assert (listSource2 <> nil);
    if listSource1^.data <= listSource2^.data then begin
	MakeNewElement (destElement, listSource1^.data);
	listSource1 := listSource1^.next;
    end else begin
	MakeNewElement (destElement, listSource2^.data);
	listSource2 := listSource2^.next;
    end;
end;

{
    Merge listSource1 and listSource2 into listDest, without modifying
    the lists pointed to by listSource1 and listSource2.
}

procedure Merge (listSource1, listSource2: ElementPtrType;
		 var listDest: ElementPtrType);
var
    tailDest: ElementPtrType;
begin
    if listSource1 = nil then begin
	MakeCopy (listDest, listSource2);
    end else if listSource2 = nil then begin
	MakeCopy (listDest, listSource1);
    end else begin
	listDest := nil;
	tailDest := listDest;
	while (listSource1 <> nil) and (listSource2 <> nil) do begin
	    CopySmallerAndMoveUp (tailDest^.next, listSource1, listSource2);
	end;
	MakeCopy (tailDest^.next, listSource1);
	MakeCopy (tailDest^.next, listSource2);
    end;
end;

begin
    ReadList (list1);
    ReadList (list2);
    Merge (list1, list2, list3);
    writeln ('*** Merged list');
    WriteList (list3);
    writeln ('*** Argument lists');
    WriteList (list1);
    WriteList (list2);
end.