Mergesort:

We sort on power as usual.

    // ************************************************ //
    // split a Complex_POLY list into the set             //
    // of odd indices and even indices                  //
    // ************************************************ //
Complex_POLY_CELL* Complex_POLY::split(Complex_POLY_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    

  Complex_POLY_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 Complex_POLY_CELLS into one chain          //
    // of odd indices and even indices                            //
    // ********************************************************** //
 
Complex_POLY_CELL* Complex_POLY::merge(Complex_POLY_CELL* A1,Complex_POLY_CELL* A2)
{
  Complex_POLY_CELL *temp1,*temp2;
  temp1 = A1;
  temp2 = A2;
  if(temp1==NULL){
    return(temp2);
    }
  if(temp2==NULL){
    return(temp1);
    }
  if(temp1->power >= temp2->power){
    //Neither list is empty and A1 has larger
    //first power than A2. So new list is
    //first power 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 Complex_POLY_CELLs      //
    // ******************************************** //
Complex_POLY_CELL* Complex_POLY::mergesort(Complex_POLY_CELL* A)
{
  Complex_POLY_CELL *temp1,*temp2;
  temp1 = A;
  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));
    }
}

    // ****************************** //
    // merge sort for Complex_POLY      //
    // ****************************** //  
void Complex_POLY::mergesort(){head = mergesort(head);}