#include "List.h"

List mergeSort(List); /* prototype */

List splitAndMerge(List inL, List half1, List half2)
/* NB. half1 and half2 are `accumulating' parameters, -- L.Allison */
 { if( inL == NULL )
      return merge(mergeSort(half1), mergeSort(half2));
   /*else, split inL */
      return splitAndMerge(inL->tl, half2, cons(inL->hd, half1));
 }/*splitAnd...*/

List mergeSort(List L)
 { if( L==NULL ) return NULL;                      /* L==[] */
   /*else*/if( L->tl == NULL ) return L;           /* L==[E] */
   /*else*/return splitAndMerge(L, NULL, NULL);    /* L==[E1,E2, ...] */
  }

/* Merge Sort a List */