//---------------------------------------------------------------------
// File: mergesort.cpp
// Name: Chip Dixon, modified by Sharon M. Tuttle
// last modified: 3-24-05
//
// Contract: mergesort: node* -> node*
//
// Purpose: sorts the nodes in the linked list pointed to by
//    <headPtr> so that the nodes are in ascending order
//    of the data field values
//
// preconditions: none
//
// postconditions: The linked list has been changed; <headPtr> now
//    points to the node whose data field is smallest, and the
//    next fields have been modified so that the linked list is
//    in ascending order of data fields.
//
// Examples:
//    base case #1:
//    for node* h1 = NULL,
//        mergesort(h1) == NULL
//
//    base case #2:
//    for node* h2 pointing to a node containing 3 (with NULL in its
//    next field),
//        mergesort(h2) == h2  
//
//    recursive case:
//    for node* h3 pointing to a linked list containing:
//    3  6  2  9  1  5,
//        mergesort(h3) will result in a pointer pointing to a linked
//           list containing:   1  2  3  5  6  9     
//
// libraries/other functions used: node.h, divide.h, merge.h
//---------------------------------------------------------------------

#include "node.h"
#include "divide.h"
#include "merge.h"
using namespace std;

node* mergesort(node* headPtr)
{
    node* subList2;
    node* result;

    // base case #1 --- list is empty
    if (headPtr == NULL)
    {
        return NULL;
    }

    // base case #2 -- list contains 1 element
    else if (headPtr->get_next() == NULL)
    {
        return headPtr;
    }

    // recursive case --- list contains >= 2 elements
    else 
    {
        result = headPtr;    // muck with copy, not original parameter

        subList2 = divide(result);
        result = mergesort(result);
        subList2 = mergesort(subList2);
        result = merge(result, subList2);

        return result;
    }
}