class node
{
  public:
    typedef int data_t;
 
    node(data_t d) { next = NULL; data = d; }
 
    node *next;
    data_t data;
};
 
class linked_list
{
  private:
    node *head;
 
  public:
    linked_list()
    {
        head = NULL;
    }
 
    int size()
    {
        int length = 0;
        node *sizeptr = head;
        while(sizeptr != NULL)
        {
            sizeptr = sizeptr->next;
            length++;
        }
        return length;
    }
 
    void add(int n, node::data_t d)
    {
        int number=0;
        node *tmp;
        node *nhp = new node(d);
        if(head == NULL){
            head=nhp;
        }else if(n == 0){
            nhp->next = head;
            head = nhp;
        }else{
            tmp=head;
            while((tmp->next != NULL) & (number < n-1)){
                tmp = tmp->next;
                number++;
            }
            nhp->next=tmp->next;
            tmp->next=nhp;
        }
    }
 
    void add_last(node::data_t d)
    {
        add(size(),d);
    }
 
    void add_first(node::data_t d)
    {
        add(0,d);
    }
 
    node::data_t get(int n)
    {
        int number=0;
        node *gptr = head;
        if(head == NULL){
            cout << "List is empty!" <<endl;
                return 0;
        }else if(n == 0){
            return gptr->data;
        }else if(n == size()-1){
            while(gptr->next != NULL)
            {
                gptr=gptr->next;
            }
            return gptr->data;
 
        }else if(n >= size()-1){
            cout << "non existent index" << endl;
            return 0;
        }else if((n > 0) & (n <= size()-1)){
            while(number < n)
            {
                gptr = gptr->next;
                number++;
            }
            return gptr->data;
        }
 
                return 0;
    }
 
    node::data_t get_first()
    {
        return get(0);
    }
 
    node::data_t get_last()
    {
        return get(size()-1);
    }
 
    void remove(int n)
    {
        int number=0;
        node *tmp, *current;
        if(head == NULL){
         cout << "The list is empty!" << endl;
        }else{
            current=head;
            if(current->next==NULL){
                delete(current);
                head=NULL;
            }else if(n == 0){
                current=head;
                head=head->next;
                delete(current);
            }else if(n > size()-1){
                cout << "nonexistent indez" << endl;
            }else{
                while((current->next != NULL) & (number < n))
                {
                    tmp = current;
                    current = current->next;
                    number++;
                }
            tmp->next=current->next;
            delete(current);
            }
        }
  }
 
    void remove_first()
    {
        remove(0);
    }
 
    void remove_last()
    {
        remove(size()-1);
    }
 
    void dump()
    {
        node *tptr;
 
        cout << "     DUMP: (size = " << size() << ", first = " << get_first()
<<", last = " << get_last() << ")\n" ;
        if (head == NULL) {
            cout << "    DUMP: head = NULL\n\n";
            return;
        }
        tptr = head;
 
        cout << "    DUMP:   head = : " << tptr->data << endl;
        while (tptr->next != NULL) {
            tptr = tptr->next;
        cout << "    DUMP:   data = : " << tptr->data << endl;
        }
        cout << endl;
    }
};
class mergesort
{
 
  public:
 
    mergesort(int ar[], int len);
 
    void mergesortlink(linked_list& list);
 
    void merge(linked_list& list1, linked_list& list2, linked_list& list);
};
 
 
 
 
  mergesort::mergesort(int ar[], int len)
  {
      int i;
 
      linked_list alist;
 
 
      for (i=0; i<len; i++){
      alist.add_last(ar[i]);
      }
      alist.dump();
 
      mergesortlink(alist);
 
      for(i=0;i<len;i++)
      {
          ar[i] = alist.get_first();
          alist.remove_first();
      }
  }
 
 
  void mergesort::mergesortlink(linked_list& list)
  {
      int i;
      int d;
      linked_list list1;
      linked_list list2;
 
      int n = list.size();
      if(n < 2){
          return;
      }
      for (i=1; i <= (n+1)/2; i++)
      {
          d = list.get_first();
          list.remove(0);
          list1.add_last(d);
   }
 
      for (i=1; i <= n/2; i++)
      {
          d = list.get_first();
          list.remove(0);
          list2.add_last(d);
      }
 
    mergesortlink(list1);
    mergesortlink(list2);
 
    merge(list1,list2,list);
 
  }
 
 
  void mergesort::merge(linked_list& list1, linked_list& list2, linked_list& list)
  {
      int d,d1,d2;
 
      while(list1.size()!=0 && list2.size()!=0)
      {
 
          d1 = list1.get_first();
          d2 = list2.get_first();
 
          if(d1 < d2)
          {
              d = list1.get_first();
              list1.remove(0);
              list.add_last(d);
              list.dump();
          }else{
              d = list2.get_first();
              list2.remove(0);
              list.add_last(d);
              list.dump();
          }
      }
 
      if(list1.size()==0)
      {
 
          while(list2.size()!=0)
          {
              d = list2.get_first();
              list2.remove(0);
              list.add_last(d);
              list.dump();
          }
      }
 
      if(list2.size()==0)
      {
          while(list1.size()!=0)
          {
              d = list1.get_first();
              list1.remove(0);
              list.add_last(d);
              list.dump();
          }
 
      }
 
  }
int main(void)
{
 
    int ar[100];
 
    int i, v, len;
 
    for (i=0; i<100; i++) {
        cout << "enter a number (-1 to quit): ";
        cin >> v;
 
        if (v < 0) break;
 
        ar[i] = v;
    }
 
    len = i;
 
    cout << "main:  before sort:\n";
    for (i=0; i<len; i++) {
        cout << "main:  ar[" << i << "] = " << ar[i] << endl;
    }
 
    mergesort ms(ar, len);
    cout << "main:  after sort:\n";
    for (i=0; i<len; i++) {
        cout << "main:  ar[" << i << "] = " << ar[i] << endl;
    }
 
//      return 0;