/*
 * merge_sort.c
 * This program sorts a sequence of number using the merge-sort algorithm.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

/* Definition of a list element: */
struct _Element
{
  int              value;    /* The stored value. */
  struct _Element  *p_next;  /* Points to the next observation. */
};

typedef struct _Element Element;

/* Prototypes: */
void print_list (const Element *p_head);
void merge_sort (Element **p_p_head, int size);

int main ()
{
  int         n;                /* How many numbers to sort. */
  int         max;              /* The maximal value of the numbers. */
  Element     *p_head = NULL;   /* Points to the head of the list. */
  Element     *p_curr = NULL;   /* The current element. */
  int         i;

  /* Read the input from the user. */
  do
  {
    printf ("Please enter the number of numbers to sort: ");
    scanf ("%d", &n);
  } while (n <= 0);

  do
  {
    printf ("Please enter the maximal number allowed: ");
    scanf ("%d", &max);
  } while (max <= 0);

  /* To make things more random: */
  srand (time(NULL));

  /* Create a list of n random number in the range of [0 - max]. */
  for (i = 0; i < n; i++)
  {
    /* Create a new element storing a random number. */
    p_curr = (Element *) malloc (sizeof(Element));
    p_curr->value = (int) (max * (rand() / (RAND_MAX + 1.0)));
    
    /* Link it to be the first element in the list. */
    p_curr->p_next = p_head;
    p_head = p_curr;
  }

  /* Print the list. */
  printf ("The original list: ");
  print_list (p_head);

  /* Sort the list. */
  merge_sort (&p_head, n);

  printf ("The sorted list: ");
  print_list (p_head);

  /* Free the list. */
  while (p_head != NULL)
  {
    p_curr = p_head;
    p_head = p_head->p_next;
    free (p_curr);
  }

  return (1);
}

/* ------------------------------------------------------------------------
 * Function: print_list
 * Purpose:  Print a list.
 * Input:    p_head - The first element in the list.
 * Returns:  Nothing.
 */
void print_list (const Element *p_head)
{
  while (p_head != NULL)
  {
    /* Print the current element. */
    printf ("%d ", p_head->value);
    
    /* Move to the next element. */
    p_head = p_head->p_next;
  }

  printf ("\n");
  return;
}

/* ------------------------------------------------------------------------
 * Function: merge_sort
 * Purpose:  Sort the list using the merge-sort alogrithm.
 * Input:    size - The list size (number of elements in the list).
 * In/Out:   p_p_head - The first element in the list.
 * Returns:  Nothing.
 */
void merge_sort (Element **p_p_head, int size)
{
  Element       *p_head_1;         /* The first list.*/
  int           size_1;            /* Its size. */
  Element       *p_head_2;         /* The second list.*/
  int           size_2;            /* Its size. */
  Element       *p_curr;
  Element       *p_merged_head = NULL;
  Element       *p_merged_tail = NULL;
  int           i;

  /* Do nothing if the list has only one element. */
  if (size < 2)
    return;

  /* Split the list into two list of equals sizes. */
  size_1 = size / 2;
  p_head_1 = *p_p_head;

  p_curr = *p_p_head;
  for (i = 0; i < size_1 - 1; i++)
    p_curr = p_curr->p_next;

  size_2 = size - size_1;
  p_head_2 = p_curr->p_next;
  p_curr->p_next = NULL;

  /* Sort the two list recursively. */
  merge_sort (&p_head_1, size_1);
  merge_sort (&p_head_2, size_2);

  /* Merge the two lists into one sorted list. */
  while (p_head_1 != NULL && p_head_2 != NULL)
  {
    /* Check which list contains the minimal value in its first element,
     * and move this element to be the tail of the merged list. */
    if (p_head_1->value < p_head_2->value)
    {
      p_curr = p_head_1;
      p_head_1 = p_head_1->p_next;
    }
    else
    {
      p_curr = p_head_2;
      p_head_2 = p_head_2->p_next;
    }
    
    if (p_merged_head == NULL)
    {
      /* This is the first element in the merged list: */
      p_merged_head = p_merged_tail = p_curr;
    }
    else
    {
      /* Add the element at the tail of the merged list: */
      p_merged_tail->p_next = p_curr;
      p_merged_tail = p_curr;
    }
    p_curr->p_next = NULL;
  }
  
  /* Add any left-overs at the tail of the merged list. */
  if (p_head_1 != NULL)
  {
    p_merged_tail->p_next = p_head_1;
  }
  else if (p_head_2 != NULL)
  {
    p_merged_tail->p_next = p_head_2;
  }

  /* Update the pointer to the head of the merged list. */
  *p_p_head = p_merged_head;

  return;
}