The MergeSort Agents for the CHAR_DL_CELL Class:

    // ********************************************************** //
    // split a chain of CHAR_DL_CELLS into the set                //
    // of odd indices and even indices                            //
    // ********************************************************** //
 
CHAR_DL_CELL* CHAR_DL_CELL::split(CHAR_DL_CELL* A)
{
  //every other element of the chain A is stored in the new
  //chain ``second'' and so A is smaller by about half.
  //output incoming list
  int diagnostic = 0;
  
  if(diagnostic==1)
    cout << "split called on ";
  if(A!=NULL){
    CHAR_DL_CELL *temp;
    temp = A;
    while(!(temp==NULL)){
      if(diagnostic==1)
        cout << *temp;
      temp = temp->next;
      }
    if(diagnostic==1)
      cout << endl;
    }
  else{
    if(diagnostic==1)
      cout << "NULL." << endl;
    }
  CHAR_DL_CELL *temp1,*temp2;
  temp1 = A;
  if(temp1==NULL) return (NULL);
  else if(temp1->next==NULL) return (NULL);
  else{
    temp2 = temp1->next;
    temp1->next = temp2->next;
    temp2->next = split(temp2->next);
    return(temp2);
    }
}

    // ********************************************************** //
    // merge 2 chains of CHAR_DL_CELLS into one chain             //
    // of odd indices and even indices                            //
    // ********************************************************** //
 
CHAR_DL_CELL* CHAR_DL_CELL::merge(CHAR_DL_CELL* A1,CHAR_DL_CELL* A2)
{
  //output incoming list
  int diagnostic = 0;
  if(diagnostic==1)
    cout << "merge called on ";
  if(A1!=NULL){
    CHAR_DL_CELL *temp;
    temp = A1;
    while(!(temp==NULL)){
      if(diagnostic==1)
        cout << *temp;
      temp = temp->next;
      }
    if(diagnostic==1)
      cout << "  ";
    }
  else{
    if(diagnostic==1)
      cout << "NULL  ";
    }
  if(diagnostic==1)
    cout << "and ";
  if(A2!=NULL){
    CHAR_DL_CELL *temp;
    temp = A2;
    while(!(temp==NULL)){
      if(diagnostic==1)
        cout << *temp;
      temp = temp->next;
      }
    if(diagnostic==1)
      cout << endl;
    }
  else{
    if(diagnostic==1)
      cout << "NULL  " << endl;
    }

  CHAR_DL_CELL *temp1,*temp2;
  temp1 = A1;
  temp2 = A2;
  if(temp1==NULL){
    return(temp2);
    }
  if(temp2==NULL){
    return(temp1);
    }
  if(temp1->element <= temp2->element){
    //Neither list is empty and A1 has smaller
    //first element than A2. So new list is
    //first element of A1 followed by a merge of remaining
    //elements
    temp1->next = merge(temp1->next,temp2);
    return(temp1);
    }
  else{
    temp2->next = merge(temp1,temp2->next);
    return(temp2);
    }
}

    // ************************************ //
    // mergesort a chain of CHAR_DL_CELLs   //
    // ************************************ //
CHAR_DL_CELL* CHAR_DL_CELL::mergesort(CHAR_DL_CELL* A)
{
  int diagnostic = 0;
  CHAR_DL_CELL *temp1,*temp2;
  temp1 = A;
  
  //output incoming list
  if(diagnostic==1)
    cout << "mergesort called on ";
  if(A!=NULL){
    CHAR_DL_CELL *temp;
    temp = A;
    while(!(temp==NULL)){
      if(diagnostic==1)
        cout << *temp;
      temp = temp->next;
      }
    if(diagnostic==1)
      cout << endl;
    }
  else{
    if(diagnostic==1)
      cout << "NULL" << endl;
    }
  if(temp1==NULL) return NULL;
  else if (temp1->next==NULL) return temp1; 
  else{
    //at least 2 elements in list
    temp2 = split(temp1);
    return merge(mergesort(temp1),mergesort(temp2));
    }
}