/* Merges two sorted lists together into one sorted list */
struct node *merge_list(struct node *l1, struct node *l2)
{
  struct node *cur=NULL;  /* Last node in list, where we work from */
  struct node *head=NULL; /* First node in list, our return value */

  /* If there's less than two lists, nothing to merge */
  if(l1==NULL)      return(l2);
  else if(l2==NULL) return(l1);

  while(l1||l2) /* Loop while either list is not empty */
  {
    struct node *tmp;
    if((!l1)||(!l2)) /* If one of the lists is empty */
    {
      /* cur is guaranteed to not be NULL.  This loop will have
         executed at least once by the time we reach here. */
      if(!l1) cur->next=l2; /* Append l2 to the end of the list */
      else    cur->next=l1; /* Append l1 to the end of the list */
      return(head); /* Return the new list */
    }
    else if(l1->sval < l2->sval) /* append first node from l2 */
    {
      if(head==NULL) /* empty list?  Don't append, just set */
      {
        head=cur=l2;
        l2=l2->next;
      }
      else /* append, go to next node */
      {
        cur->next=l2;
        cur=cur->next;
        l2=l2->next;
        cur->next=NULL;
      }
    }
    else /* append first node from l1 */
    {
      if(head==NULL) /* empty list?  don't append, just set */
      {
        head=cur=l1;
        l1=l1->next;
      }
      else /* append, go to next node */
      {
        cur->next=l1;
        cur=cur->next;
        l1=l1->next;
        cur->next=NULL;
      }
    }
  }
  return(head); /* Return the merged list */
}

/* Recursively sorts a linked list with the mergesort algorithm */
struct node *mergesort_list(struct node *list)
{
  /* pointers to first and last nodes of new lists */
  struct node *head[2],*tail[2];

  /* Empty list, return immediately */
  if(list==NULL)
    return(NULL);

  /* Set up list #0 */
  head[0]=tail[0]=list;
  list=list->next;

  /* Only one node, no sorting to be done */
  if(list==NULL)
    return(head[0]);

  /* Set up list #1 */
  head[1]=tail[1]=list;
  list=list->next;

  /* Loop through all the rest of the nodes in list, appending to and 
     splitting the nodes evenly between tail[0] and tail[1] */
  while(list!=NULL)
  {
    tail[0]->next=list;
    tail[0]=tail[0]->next;
    list=list->next;

    if(list!=NULL)
    {
      tail[1]->next=list;
      tail[1]=tail[1]->next;
      list=list->next;
    }    
  }

  /* Properly terminate the lists */
  tail[0]->next=NULL;
  tail[1]->next=NULL;

  /* recursively mergesort the two half-lists. */
  head[0]=mergesort_list(head[0]);
  head[1]=mergesort_list(head[1]);
  /* merge the now-sorted lists together, returning new head pointer. */
  return(merge_list(head[0],head[1]));
}