Category : C Source Code
Archive   : BFSORTS.ZIP
Filename : MSORT.C

 
Output of file : MSORT.C contained in archive : BFSORTS.ZIP
/***********************************************************************/
/* SORT(): Non-Recursive Merge Sort function. */
/* See the function declaration for calling information. */
/* Function is by Bruce Feist; please contact me on CompuServe with */
/* a message on BPROGB, MACDEV, or EASYPLEX if you have any */
/* questions or problems. */
/* You can also reach me at the Enlightened Board, at (703) 370-9528, */
/* N/8/1 */
/* Feel free to make use of this code in your own programs. */
/***********************************************************************/

/* Merge sort. Fast, but uses lots of space. */

#include
#include
#include
#include

#include "sort.h"

#define VERBOSE (0)

static char *base, *last_ptr, *temp_base;
static unsigned int nelem, width;
static int (*compare) (void *, void *);
static void merge (char *, unsigned int);
#if VERBOSE
static void show_array (void *, int);
#endif

int
msort (void *pbase, size_t pnelem, size_t pwidth, int pcompare())
{
long sublist_length, sublist_offset;
unsigned int list_size;

base = pbase;
nelem = pnelem;
width = pwidth;
compare = pcompare;

#if VERBOSE
printf ("Msort (%p, %d, %d, %p).\n", pbase, pnelem, pwidth, pcompare);
#endif

list_size = nelem * width;

temp_base = malloc (list_size);
if (temp_base == NULL)
return S_NOMEM;

last_ptr = base + list_size - width;

/* We first merge sublists of length 1, then of length 2, and */
/* so on, doubling each time. */

for (sublist_length = width;
sublist_length < list_size;
sublist_length <<= 1)
{
for (sublist_offset = 0;
sublist_offset + sublist_length < list_size;
sublist_offset += sublist_length << 1)
#pragma warn -sig
merge (base + sublist_offset, (unsigned int) sublist_length);
#pragma warn .sig
} /* for sublist_length */

free (temp_base);

return S_OK;
} /* end msort */


void
merge (char *left_base, unsigned int length)
{
char *left_ptr, *right_ptr, *left_max, *right_max, *result_ptr;

#if VERBOSE
printf ("Merge (%p, %u)\n", left_base, length);
#endif

left_ptr = left_base;
right_ptr = left_base + length;
left_max = right_ptr - width;
right_max = (length > last_ptr - right_ptr) ? last_ptr : left_max + length;

#if VERBOSE
fputs ("Input: ", stdout);
show_array (left_base, (right_max - left_base + width) / sizeof (double));

if (length > 20000)
printf ("Merging %p - %p with %p - %p.\n",
left_ptr, left_max, right_ptr, right_max);
#endif


result_ptr = temp_base;
while (1)
{
if (compare (left_ptr, right_ptr) > 0)
{
memcpy (result_ptr, right_ptr, width);
right_ptr += width;
result_ptr += width;
if (right_ptr > right_max)
{
memcpy (result_ptr, left_ptr, left_max - left_ptr + width);
break;
}
}
else
{
memcpy (result_ptr, left_ptr, width);
left_ptr += width;
result_ptr += width;
if (left_ptr > left_max)
{
memcpy (result_ptr, right_ptr, right_max - right_ptr + width);
break;
}
}
} /* end while */


#if VERBOSE
printf ("Copying %d bytes from %p to %p.\n",
right_max - left_base + width, temp_base, left_base);
fputs ("Intermediate: ", stdout);
show_array (temp_base, (right_max - left_base + width) / sizeof (double));
#endif

memcpy (left_base, temp_base, right_max - left_base + width);

#if VERBOSE
fputs ("Output: ", stdout);
show_array (left_base, (right_max - left_base + width) / sizeof (double));
#endif

} /* end merge */


  3 Responses to “Category : C Source Code
Archive   : BFSORTS.ZIP
Filename : MSORT.C

  1. Very nice! Thank you for this wonderful archive. I wonder why I found it only now. Long live the BBS file archives!

  2. This is so awesome! 😀 I’d be cool if you could download an entire archive of this at once, though.

  3. But one thing that puzzles me is the “mtswslnkmcjklsdlsbdmMICROSOFT” string. There is an article about it here. It is definitely worth a read: http://www.os2museum.com/wp/mtswslnk/