home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
The C Users' Group Library 1994 August
/
wc-cdrom-cusersgrouplibrary-1994-08.iso
/
listings
/
v_11_07
/
mergesrt.c
< prev
next >
Wrap
C/C++ Source or Header
|
1993-02-04
|
4KB
|
118 lines
#include <stddef.h> /* get #define for NULL */
#include <stdlib.h>
#define UNREADY 1
#define READY 2
#define PART struct part
PART
{
unsigned start, n_elems, state;
};
/* The theology underlying this mergesort routine is to emulate */
/* the workings of a recursive routine without actually recurring */
/* and getting function call overhead. The code in MERGESRT.BAK */
/* does exactly what this code does, except that it does the */
/* recursion and is thus slower; you might want to refer to it */
/* if you get bogged down here. */
/* The actual method is as follows: */
/* 1: Think in terms of parts. The array to be sorted is one */
/* big part with start = 0, n_elems = n_elements. Sorting */
/* a part requires sorting each half of the part, then */
/* merging each half together. */
/* 2: To sort a part: if it's UNREADY, i.e. its halves are */
/* unsorted, then mark it as READY and add its two halves */
/* on as being UNREADY. If it's READY, this means that */
/* each half has been sorted, so merge the halves and */
/* 'forget' about that part, i.e., decrement the number */
/* of parts. */
/* 3: Eventually, you have no parts, and you're done. */
/* Originally written 2 Feb 93 by Bill Gray */
static void msort( char *data, char *temp_data, unsigned n_elements,
unsigned elem_size, int (*compare)(void *elem1, void *elem2))
{
char *part1, *part2, *dest;
unsigned n_parts, start, n_elems;
PART parts[32], *part_ptr;
n_parts = 1;
parts[0].start = 0;
parts[0].n_elems = n_elements;
parts[0].state = UNREADY;
while( n_parts)
{
part_ptr = parts + (n_parts - 1);
start = part_ptr->start;
n_elems = part_ptr->n_elems;
if( part_ptr->state == UNREADY)
{
if( n_elems > 1)
{
part_ptr->state = READY;
part_ptr[1].state = part_ptr[2].state = UNREADY;
part_ptr[1].start = start;
part_ptr[1].n_elems = n_elems / 2;
part_ptr[2].start = start + n_elems / 2;
part_ptr[2].n_elems = n_elems - n_elems / 2;
n_parts += 2;
}
else
n_parts--;
}
else /* part_ptr->state == READY; each half is ready for merging */
{
unsigned remains1, n1, remains2, n2;
remains1 = n1 = n_elems / 2;
remains2 = n2 = n_elems - n1;
part1 = data + start * elem_size;
part2 = part1 + n1 * elem_size;
dest = temp_data;
while( remains1 && remains2)
{
if( compare( part1, part2) < 0)
{
memcpy( dest, part1, elem_size);
part1 += elem_size;
remains1--;
}
else
{
memcpy( dest, part2, elem_size);
part2 += elem_size;
remains2--;
}
dest += elem_size;
}
/* if, as is usual, one half "runs out" before the other, */
/* copy the remainder of the other half onto the list. */
memcpy( dest, part1, remains1 * elem_size);
dest += remains1 * elem_size;
memcpy( dest, part2, remains2 * elem_size);
/* we now have a sorted version... copy it back to */
/* the original buffer, and we're done */
memcpy( data + start * elem_size, temp_data, n_elems * elem_size);
n_parts--;
}
}
}
int my_mergesort( void *data, unsigned n_elements, unsigned elem_size,
int (*compare)(void *elem1, void *elem2))
{
void *temp_data;
/* we need a temporary scratch space as big as the input array */
temp_data = calloc( n_elements, elem_size);
if( temp_data)
msort( data, temp_data, n_elements, elem_size, compare);
free( temp_data);
/* only possible error is that temp_data didn't calloc */
return( temp_data == NULL);
}