/*
 * mergesort.cpp
 * Mergesort on singly-linked lists.
 */

/* node
   The node type for our linked list.
*/
struct node 
{
    int value;
    node* next;
};

// Declarations for the functions below.
node* mergesort(node* input);
node* mergesort(node* input, int length);
node* merge(node* left, node* right);

/* mergesort(input)
   Mergesort the list whose head is `input`, returning a new sorted list. This
   function should compute the length of the list, and then pass `input` and
   the length to the two-parameter recursive `mergesort` overload, below.

   Must run in O(n log n) time (but that's because `mergesort(node*,int)`, below
   runs in O(n log n)).

   Must use O(n) space (i.e., the returned list is created new).
*/
node* mergesort(node* input)
{
    // Your code here
}

/* mergesort(input, length)
   Recursively Mergesort the `input` list (whose length is given by `length`),
   returning a new sorted list. 

   Must run in O(n log n) time, where n = `length`.

   Must use O(n) space (returned list is created new). 

   NOTE: The `input` list must not be modified in any way.
*/
node* mergesort(node* input, int length)
{
    // Your code here
}

/* merge(left, right)
   Merge the lists given by `left` and `right`, returning the head of the merged
   list (the returned node should either be the head of `left` or the head of
   `right`). The two input lists will always be sorted in ascending order.

   Must run in O(m+n) time where `m` is the length of `left` and `n` is the 
   length of `right`.

   Must use O(1) space (i.e., this is an in-place operation); no new nodes 
   may be created.

   NOTE: This function should modify the `next` pointers in the nodes, but NOT
   modify the `value`s. That is, it merges the lists by updating their list
   structure, not by moving values from one list to another.
*/              
node* merge(node* left, node* right)
{
    // Your code here
}