ellSort.c File Reference

#include <stdlib.h>
#include "epicsAssert.h"
#include "ellLib.h"

Include dependency graph for ellSort.c:

Go to the source code of this file.

Functions
void	ellSortStable (ELLLIST *pList, pListCmp cmp)
	Stable (MergeSort) of a given list. More...

Function Documentation

void ellSortStable	(	ELLLIST *	pList,
		pListCmp	pListCmp
	)

Stable (MergeSort) of a given list.

Parameters

pList	Pointer to list to be sorted
pListCmp	Compare function to be used

Note

The comparison function cmp(A,B) is expected to return -1 for A<B, 0 for A==B, and 1 for A>B.

Use of mergesort algorithm based on analysis by http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html

Definition at line 30 of file ellSort.c.

{
    ELLLIST INP, P, Q;
    size_t insize = 1; /* initial sub-list size */
    if(ellCount(pList)<=1)
        return;

    ellInit(&INP);
    ellInit(&P);
    ellInit(&Q);

    /* Process is to iteratively sort
     * a sequence of sub-lists of size 'insize'
     */

    while(insize < ellCount(pList)) {

        assert(ellCount(&INP)==0);

        /* shift previous results to inputs */
        ellConcat(&INP, pList);

        while(ellCount(&INP))
        {
            ELLNODE *p, *q;

            /* Pull out the next pair of sub-lists */
            ellMoveN(&Q, &INP, insize);
            ellMoveN(&P, &INP, insize);

            /* merge these sub-lists */
            while((p=ellFirst(&P)) && (q=ellFirst(&Q)))
            {
                if((*cmp)(p,q) < 0) {
                    ellAdd(pList, ellGet(&P));
                } else {
                    ellAdd(pList, ellGet(&Q));
                }
            }

            /* concatenate any remaining to result */
            if(ellFirst(&P))
                ellConcat(pList, &P);
            else if(ellFirst(&Q))
                ellConcat(pList, &Q);

            assert(!ellFirst(&P) && !ellFirst(&Q));
        }

        insize *= 2;
    }

}