#include "List.h"
/* NB. assumes list of int  -- L.Allison, Comp Sci, Monash Uni */

List merge(List A, List B)
 { if(A==NULL) return B;
   /*else*/
   if(B==NULL) return A;
   /*else neither A nor B is empty*/
   if(A->hd <= B->hd)
      return cons(A->hd, merge(A->tl, B));
   else/*B->hd < A->hd*/
      return cons(B->hd, merge(A, B->tl));
 }/*merge*/

/* Merge Two Sorted Lists to Produce One Sorted List */