/************************ natmerge.c ***********************************/
/*       Copyright 1998 G. White              */
/* 26/04/98 Initial public release            */
/* Implementation of natural 2-way merge sort */
/* Based on Knuth, Vol 3, page 160 - 163      */
/* You may use this code freely. You may also distribute it, provided     */
/* no charge is levied beyond that for its distribution medium.           */
/* The author makes no warranty of the code's usefulness for any purpose, */
/* and accepts no responsibility for any damages caused by its misuse.    */
/* nat_merge() sorts an array, the type is controlled by the #define T    */
/* and can be any intrinsic type.                                         */
/* mat_merge_p() uses an external comparison routine and takes the same   */
/* parameter list as the standard library qsort(). It uses the standard   */
/* library memcpy() routine to move elements.                             */
/* Both versions allocate a local work area from the heap the same size   */
/* as the array to be sorted, and return 0 if unable to allocate the work */
/* area, otherwise they return 1.                                         */
#include         /* for memcpy() prototype */
#include      /* for malloc() prototype */
/* Now specify the intrinsic type for nat_merge() */
#define T       short
/* Prototypes */
int nat_merge (T *array,int n);
int nat_merge_p (void *base,
    size_t num,
    size_t width,
    int (*compare)(const void *, const void *) );
/* Var  Values Description                      */
/* s =  0/1 array transfer direction, 0 for array to t_array */
/* d = -1/1 dest move direction                 */
/* f =  1/0 completion flag, 1 if done          */
/* i = current left position in source array    */
/* j = current right position in source array   */
/* k = destination position                     */
/* l = save for alternate destination position  */
/* temp = used when exchanging k & l            */
/* t_array = temporary array, the same size as array to sort */
/* Return Values                                       */
/* Returns 0 if unable to malloc() the temporary array */
/* Returns 1 otherwise                                 */
/******************************************************************/
int nat_merge_p (void *array,size_t n,size_t width,
                int (*compare)(const void *, const void *))
{
char    *i,*j,*k,*l,*temp,*t_array;
int     s,d,f;
if (NULL == (t_array = (char *) calloc (n,width)))
    return 0;           /* Not enough heap available, fail cleanly */
s = 0;                  /* Sort from array to t_array */
do
    {
    if (s == 0)
        {                       /* Transfer from array to t_array */
        i = (char *)array;
        j = (char *)array + (n - 1) * width;
        k = t_array;
        l = t_array + (n - 1) * width;
        }
    else
        {                       /* transfer t_array to array */
        k = (char *)array;
        l = (char *)array + (n - 1) * width;
        i = t_array;
        j = t_array + (n - 1) * width;
        }
    d = f = 1;                  /* set increasing k and done flag */
    while (i != j)
        {
        if ((*compare)(i,j) <= 0)
            {                           /* Start from left of source array */
            memcpy (k,i,width);         /* and transfer to destination      
/
            k += d * width;             /* move k in the required direction 
/
            i += width;                 /* and incremet i to the next */
            if ((*compare)(i - width,i) > 0)
                {       /* until the next element is out of sequence */
                do
                    {
                    memcpy (k,j,width); /* then transfer from the other end 
/
                    k += d * width;
                    j -= width;
                    }           /* until out of sequence */
                while ((*compare)((j + width),j) <= 0);
                f = 0;          /* clear completion flag, now store data */
                d = -d;         /* in reversed order to the last one     */
                temp = k;       /* to the current position from the      */
                k = l;          /* other end of the array                */
                l = temp;
                }
            }
        else
            {                   /* start from right of source */
            memcpy (k,j,width); /* and otherwise as above */
            k += d * width;
            j -= width;
            if ((*compare)((j + width),j) > 0)
                {
                do
                    {
                    memcpy (k,i,width);
                    k += d * width;
                    i += width;
                    }
                while ((*compare)((i - width),i) <= 0);
                f = 0;
                d = -d;
                temp = k;
                k = l;
                l = temp;
                }
            }
        }
    memcpy (k,i,width);         /* transfer the last element */
    s = 1 - s;                  /* and swap array usage      */
    }
while (0 == f);
if (s)                          /* if data in t_array, move it to array */
    for (i = array,j = t_array,s = 0;s < n * width;s++)
        *i++ = *j++;
free (t_array);                 /* tidy up */
return 1;                       /* and show all went well */
}
>>> Continued to next message
 * SLMR 2.1a * Wastebasket: Something to throw things near.
--- Maximus/2 3.01
---------------