/* Introduction
to program:
Program
- mergest.c.
Sorts
a list using the mergesort algorithm.
Francis
O'Donovan 20-2-98. */
/* Files to be #included. */
#include <stdio.h>
/* #definitions. */
#define LENGTH 100 /* Number of elements in list. */
/* Function: main() */
void main()
{
/* Function definitions. */
void mergesort();
void merge();
/* Variable definitions. */
int i,j;
/* Counters. */
int steps;
/* How many steps it took to sort it. */
int A[LENGTH];
/* List which will be sorted. */
/* Print introduction on screen. */
printf( "Program: mergest.c.\n\n" );
printf( "Sorts a list using the mergesort" );
printf( " algorithm.\n\n" );
printf( "Francis O'Donovan 20-2-98.\n\n" );
/* Initialize array. */
j = LENGTH - 1;
/* Will start at largest value, so list
will be in reverse order. */
for( i=0; i<LENGTH; i++)
{
A[i] = j;
j--;
}
/* Print out original array. */
printf( "The original array was:\n" );
for( i=0; i<LENGTH; i++)
{
printf( "%d ", A[i] );
}
printf( ".\n" );
/* Call mergesort on original array. */
steps = 0;
mergesort( A, 0, (LENGTH - 1), &steps );
/* Print out sorted array. */
printf( "The sorted array is:\n" );
for( i=0; i<LENGTH; i++)
{
printf( "%d ", A[i] );
}
printf( ".\n" );
printf( "The number of steps was %d.\n", steps );
}
/*********************************************************************/
/* Function:
mergesort().
Purpose:
Sorts a list using mergesort algorithm.
Arguements:
A pointer to the first element of the list,
and two int showing where in the list to sort.
Returns:
void.
*/
void mergesort( first_el, p, r, steps )
int
*first_el, p, r, *steps;
/*
This is running the list < A[p],...,A[r] >. */
{
/*
Local variable definitions. */
int q; /*
The list is divided at this point. */
/*
Check that the list is not a single element list. */
if( p < r )
/* Now we can divide the list. */
{
q = (p+r)/2 ; /* Set q to middle of list. */
/* Since q is int, this will be truncated. */
mergesort( first_el, p, q, steps ); /* Do mergesort on first half
of list.*/
mergesort( first_el, q+1, r, steps ); /* Second half of list.
*/
merge( first_el, p, q, r, steps ); /* Combine the two. */
}
}
/********************************************************************/
/* Function:
merge().
Purpose:
Merges two lists together.
Arguements:
A pointer to the first element of the list,
and three int showing where in the list to merge.
Returns:
void.
*/
void merge( first_el, p, q, r, steps )
int
*first_el, p, q, r, *steps;
/*
This merges < A[p],...,A[q] > with < A[q+1],..,A[r] >.
*/
{
/*
Local variables definitions. */
int i=0, j=0; /* These say what is on top of each
pile. */
/* Thus right now A[p+0] and A[q+1+0] are the top cards. */
int B[LENGTH]; /* The new
array B */
int m; /*
Counter. */
int k=0; /* This will
be the index of the new array we throw cards into. */
/* Merge list. */
while( (p+i <= q ) || (q+1+j <= r) )
/* As long as one pile is still there. */
{
*steps += 1;
if( (q+1+j > r) && ( p+i <= q ))
/* 2nd pile empty and 1st pile not empty. */
{
B[k] = *(first_el+p+i); /* Card from first pile is added
to new list. */
k++; /* Move on in new pile. */
i++; /* Move on in old pile. */
}
else if( ( p+i > q ) && (q+1+j <= r))
/* 1st pile empty and 2nd pile not empty. */
{
B[k] = *( first_el+q+1+j );
/* Card from 2nd pile is added to new list in hand. */
k++;
j++;
}
else if( ( *(first_el+p+i) < *(first_el+q+1+j) ))
/* Card on 1st pile < card on 2nd pile. */
{
B[k] = *(first_el+p+i); /* Card from first pile is added
to new list. */
k++; /* Move on in new pile. */
i++; /* Move on in old pile. */
}
else
/* Card on 2nd pile < card on 1st pile. */
{
B[k] = *( first_el+q+1+j );
/* Card from 2nd pile is added to new list in hand. */
k++;
j++;
}
}
/* Fill old list with merged list from B. */
for( m=0; m <= (r-p); m++ )
{ *(first_el+p+m) =
B[m];
}
}
© Francis O'Donovan
1999.
