lmsort 

    #include <mplib1/lmsort.h>

    struct lmsortp
    {
	struct lmsortp	*next;
	void		*dp;
    };

    typedef int lmsortp_t (const void *, const void *);


    struct lmsortp *lmsort( struct lmsortp * start, lmsortp_t compar );

    struct lmsortp *
	lmsort_init( void* base, size_t nel, size_t width, struct lmsortp *dp );

    void
	lmsort_end( struct lmsortp *dp );
This function provides an optimised list-merge sort which is capable (as implemented) of sorting up to 33,554,430 records. Tests have indicated that it is probabaly the fastest general purpose sort available.

This is a publically available routine, the documentation from which follows.

Optimal list-merge sorting algorithm with exponential merge schedule.

Software Development International, Winter 1991.

This implementation by Jeremy Harris jgh@imptld.com

Adapted into toolkit by Martin Poole Martin.Poole@ukuug.org

How to use these routines.

Consider how an array of elements would typically be sorted using qsort() 

    struct some_struct them[ARRAY_SIZE];
    int t;

    qsort(  &them[0],
	    ARRAY_SIZE,
	    sizeof(struct some_struct),
	    some_struct_comparison_function );

    for ( t=0; t<ARRAY_SIZE; t++ )
	some_struct_print_function( &some_struct[t] );
qsort works by shuffling the values around as determined by the comparison function. This has the disadvantage of transferring a lot of data, which is probably an unnecessary and large overhead if the only use for the data is to print some part of it.

The lmsort routines behave differently because they do not shuffle the data itself, only a linked list of pointers to the data. To sort the above array using lmsort you need two extra variables, and a pair of extra calls. 

    struct some_struct them[ARRAY_SIZE];
    struct lmsortp *lp1, *lp2;

    lp1 = lmsort_init(  &them[0],
			ARRAY_SIZE,
			sizeof(struct some_struct),
			NULL );
    lp2 = lmsort( lp1, some_struct_comparison_function );

    while (lp2)
    {
	some_struct_print_function( lp2->dp );
	lp2 = lp2->next;
    };

    lmsort_end( lp1 );
The three functions perform the following actions.
lmsort_init
This routine allocates an array of lmsortp structures and initialises the data pointers and link chain.
lmsort
This routine performs the sort, and returns a pointer to the first lmsortp structure. Note that the value returned is not necessarily the same as the supplied parameter.
lmsort_end
This routine simply frees up the array allocated by the call to lmsort_init.
It is not a requirement to use the _init and _end functions. If your data structure has a sub-structure that is a struct lmsortp then all that is required is that the ->next list is initialised (with a NULL pointer on the last item), and that the data pointers are set.