
  // LinkNode.cpp Wed Feb 12 17:06:42 PST 2003

#include"LinkNode.h"
#include<iostream.h>

     LinkNode::LinkNode(int n){
       item = n;
       next = 0;
      }

     LinkNode::~LinkNode(){
       if(next != 0) delete next;
      }

     void LinkNode::merge(LinkNode * other){
       if (other != 0){
         compCount++;
         if (item > other->item){
           int saveItem = item;
           LinkNode * saveNext = next;
           item = other->item;
           next = other->next;
           other->item = saveItem;
           other->next = saveNext;
          };
         if (next == 0)
          next = other;
         else
          next->merge(other);
        }
      }

     void LinkNode::sortList(int ell){ // implemented using mergesort
       if (ell == 2){
         compCount++;
         if (next->item < item){
           int saveItem = item;
           item = next->item;
           next->item = saveItem;
          }
         }
       else if (ell > 2){ // if ell <= 1 there is nothing to do
         LinkNode * runner = next;
         for (int i=2;i < (ell+1)/2; i++)
          runner = runner->next;
         LinkNode * half = runner->next;
         runner->next = 0;
         sortList((ell+1)/2);
         half->sortList(ell-(ell+1)/2);
         merge(half);
        }
      }

     int LinkNode::compCount=0;

