The Merge Sort Code:

The agents merge, split and mergesort will implement the standard sorting method called MergeSort. Given a chained set of CHAR_SL_CELL objects (such a chain with minor additions will later be identified with a singly linked list object CHAR_SLLIST ), the MergeSort algorithm is starts with a chain and subdivides the original chain using the agent split into two new chains by storing every other chain element of the original chain into a second chain. These two new chains are sorted and then merged via the agent merge. The MergeSort algorithm recursively calls mergesort until the splitting process results in a subchain that consists of only two elements which are easily split and sorted. So there are three functions here:

The code to split a list into two halves: split()

The code to merge two lists into one list: merge()

The code to mergesort a list: mergesort()

Here are the code fragments for these functions:

    // ********************************************************** //
    // split a chain of CHAR_SL_CELLS into the set                //
    // of odd indices and even indices                            //
    // ********************************************************** //
 
CHAR_SL_CELL* CHAR_SL_CELL::split(CHAR_SL_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_SL_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_SL_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_SL_CELLS into one chain             //
    // of odd indices and even indices                            //
    // ********************************************************** //
 
CHAR_SL_CELL* CHAR_SL_CELL::merge(CHAR_SL_CELL* A1,CHAR_SL_CELL* A2)
{
  //output incoming list
  int diagnostic = 0;
  if(diagnostic==1)
    cout << "merge called on ";
  if(A1!=NULL){
    CHAR_SL_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_SL_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_SL_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_SL_CELLs   //
    // ************************************ //
 
CHAR_SL_CELL* CHAR_SL_CELL::mergesort(CHAR_SL_CELL* A)
{
  int diagnostic = 0;
  CHAR_SL_CELL *temp1,*temp2;
  temp1 = A;
  
  //output incoming list
  if(diagnostic==1)
    cout << "mergesort called on ";
  if(A!=NULL){
    CHAR_SL_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));
    }
}