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