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

 
Output of file : MLSORT.C contained in archive : BFSORTS.ZIP
/***********************************************************************/
/* SORT(): Non-Recursive Merge List 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/List sort. Fast, but uses even more space than msort. */
/* Like merge sort, but takes advantage of any preexisting ordered sublists. */

#include
#include
#include
#include
#include

#include "sort.h"

#define ENDLIST -1
#define VERBOSE (0)

static char *base;
static unsigned int nelem, width;
static int (*compare) (void *, void *);
static int merge (int left, int right);
static void show_lists (int *lists, int nlists);
static void show_list (int list);

static int *next; /* array: which element comes after this one? */

int
mlsort (void *pbase, size_t pnelem, size_t pwidth, int pcompare())
{
int *lists; /* array of pointers to sorted sublists */
unsigned int nlists, list_num;
int elem_num, temp_num;
char *temp_base;
int workspace_size;
void *workspace; /* contains lists or temp_base, depending on when */

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

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

workspace_size = nelem * max (sizeof (*lists) + sizeof (*next), width);
workspace = malloc (workspace_size);
if (workspace == NULL)
return S_NOMEM;

temp_base = workspace;
lists = workspace; /* it's never used concurrently with temp_base! */

next = malloc (nelem * sizeof (*next));
if (next == NULL)
return S_NOMEM;

lists[0] = 0;
nlists = 1;

for (elem_num = 1;
elem_num < nelem;
elem_num++)
{
if (compare(base + (elem_num - 1) * width,
base + elem_num * width) > 0)
{
next [elem_num - 1] = ENDLIST;
lists [nlists] = elem_num;
nlists++;
}
else
{
next [elem_num - 1] = elem_num;
}
} /* end for */
next [nelem - 1] = ENDLIST;

while (nlists > 1)
{ /* Merge pairs of lists */
for (list_num = 0;
list_num < (nlists - 1);
list_num++, nlists--)
{
#if VERBOSE
show_lists (lists, nlists);
printf ("\nMerging list %d with list %d:\n", list_num, list_num + 1);
#endif
lists[list_num] = merge (lists[list_num], lists[list_num + 1]);
lists[list_num + 1] = lists[nlists - 1];
} /* end for */
} /* end while */

#if VERBOSE
show_lists (lists, nlists);
#endif

/* move everything to where it belongs. */

for (elem_num = 0, temp_num = lists[0];
elem_num < nelem;
elem_num++, temp_num = next [temp_num])
{
memcpy (temp_base + width * elem_num, base + width * temp_num, width);
}

memcpy (base, temp_base, width * nelem);

return S_OK;
} /* end msort */


int
merge (int left, int right)
{
int first, last;
char *left_ptr, *right_ptr;

left_ptr = base + left * width;
right_ptr = base + right * width;

if (compare (left_ptr, right_ptr) > 0)
{
first = last = right;
right = next [right];
right_ptr = base + right * width;
}
else
{
first = last = left;
left = next [left];
left_ptr = base + left * width;
}

while (left != ENDLIST && right != ENDLIST)
{
if (compare (left_ptr, right_ptr) > 0)
{
/* right is smaller; use it */
next [last] = right;
last = right;
right = next [right];
right_ptr = base + right * width;
}
else
{
/* left is smaller; use it */
next [last] = left;
last = left;
left = next [left];
left_ptr = base + left * width;
}
}

next [last] = (left == ENDLIST) ? right : left;

return first;
} /* end merge */


void
show_lists (int *lists, int nlists)
{
int list;

for (list = 0;
list < nlists;
list++)
{
printf ("List # %d at ", list);
show_list (lists [list]);
} /* end for */
} /* end show_lists */


#pragma warn -use
void
show_list (int list)
{
int node;

printf ("%d: ", list);
for (node = list;
node != ENDLIST;
node = next [node])
{
printf ("# %d: %.4lf, ", node, *((double *) (base + node * width)));
}
printf ("\n");
} /* end show */


  3 Responses to “Category : C Source Code
Archive   : BFSORTS.ZIP
Filename : MLSORT.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/