// functions use by main
void mergesort(linked_list& list);

// Merges sorted list dl1 and dl2 into a sorted list dl
void merge(linked_list& list1, linked_list& list2, linked_list& list);


// merge sort on  link list
void mergesort(linked_list& list)
{


int i;
int d;
linked_list list1;
linked_list list2;

int n = list.size();
if(n < 2)return;

// copy 1/2 to list1
for (i=1; i <= (n+1)/2; i++)
        {
        d = list.get_first();
        list.remove(0);
        list1.add_last(d);
        }


// copy remaining 1/2 to list2
for (i=1; i <= n/2; i++)
        {
        d = list.get_first();
        list.remove(0);
        list2.add_last(d);
        }

        // sort both lists by recursion
        mergesort(list1);
        mergesort(list2);

        // merge two lists
        merge(list1,list2,list);

}


// Merges sorted list dl1 and dl2 into a sorted list dl
void merge(linked_list& list1, linked_list& list2, linked_list& list)
{
int d,d1,d2;

// loop till both lists empty
while(!list1.size()==0 && !list2.size()==0)
       {

        // get data items from start of both lists
        d1 = list1.get_first();
        d2 = list2.get_first();

        // check if first element of dl1 is less than dl2

        // from list1
        if(d1 < d2)
        {
        d = list1.get_first();
        list1.remove(0);
        list.add_last(d);
        }

        // from list2
        else
        {
        d = list2.get_first();
        list2.remove(0);
        list.add_last(d);
        }
        }

// empty list dl1 into dl
if(list1.size()==0)
{

        // get rest of list2
        while(!list2.size()==0)
        {
        d = list2.get_first();
        list2.remove(0);
        list.add_last(d);
        }
}


// empty list dl2 into dl
if(list2.size()==0)
{
        // get rest of list1
        while(!list1.size()==0)
        {
        d = list1.get_first();
        list1.remove(0);
        list.add_last(d);
        }
}

}

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;
    }
}