An implementation of the dominance tree sort

  
/*
 * Copyright (c) 2004 by Richard Harter.
 * This software may be freely used and modified without
 * restriction provided that this notice is preserved unaltered.
 *
 */
 
/*
 * PURPOSE:
 * This is an implementation of a dominance tree sort.  See
 * http://home.tiac.net/~cri/domsort.html for a description
 * dominance tree sorts.  It sorts the data in place.  It uses
 * the minimum number of data moves and is nearly optimal for
 * minimizing the number of comparisons used.
 */

#include <stdlib.h>
#define ENDLIST -1
#define PROCESSED -1
#define NODE struct domsortnode


#define DATATYPE int
#define MAXC 64
#define COMPARE_LT(x,y) (x < y)

struct domsortnode {
        int child;
        int sibling;
};

        
int
domsort(DATATYPE * data, int n)
{
   NODE    *node;            /* Data structure for sort lists        */
   int      u_head;          /* Head of unbeaten list                */
   int      u_tail;          /* Tail of unbeaten list                */
   int      first;           /* First of a comparison pair           */
   int      second;          /* Second of a comparison pair          */
   int      root;            /* Tree root element                    */
   int      i;               /* Loop index through array             */
   int      j;               /* Index of current perm. index         */
   int      k;               /* Index of next perm. index            */
   int      pos_counter;     /* Position in sorted file of tree root */
   int      children[MAXC];  /* Children list in array form          */
   int      sib;             /* Sibling from a sibling list          */
   int      count;           /* Size and index of sibling list       */
   int      compares = 0;    /* No. compares counter                 */
   DATATYPE save;            /* Save element for swapping            */
    

    node   = malloc(n*sizeof (NODE));
    if ((!node)) return 0;
    for (i=0; i<n; i++) 
    {
        node[i].child            = ENDLIST;
        node[i].sibling          = i+1;
    }
    node[n-1].sibling            = 0;
    u_head                       = 0;
    u_tail                       = n-1;

/*
 *  Knockout pairing section.  All of the initially unbeaten elements
 *  are linked together in a sibling (circular linked) list.  Elements
 *  are removed two at a time from the list and compared.  The winner
 *  is appended to the tail of the unbeaten list.  The loser is added
 *  to the sibling list for the winner's children.
 *
 */
    for (count = n-1; --count>=0;) {
        first                    = u_head;
        second                   = node[first].sibling;
        u_head                   = node[second].sibling;
        compares++;
        if (COMPARE_LT(data[first], data[second])) 
        {
           node[u_tail].sibling     = first;
           u_tail                   = first;
           node[second].sibling      = node[first].child;
           node[first].child       = second;
        } else {
           node[u_tail].sibling     = second;
           u_tail                   = second;
           node[first].sibling      = node[second].child;
           node[second].child       = first;
        }
    }
/*
 *  The data now forms a dominance tree (heap) with a single root.
 *  We now have a loop; in each iteration the root is removed from
 *  from the tree and the children of the root are compared sequentially
 *  to find the new root.
 *
 *  The sibling field of the removed root holds the final position of
 *  the corresponding data element.
 */

 
    root                             = u_tail;
    pos_counter                      = 0;
    for(;;) {
        node[root].sibling          = pos_counter++;
        for(sib=node[root].child, count=0;
            sib != ENDLIST; 
            sib=node[sib].sibling) 
            { children[count++] = sib;}
        if (count == 0) break;
        if (count == 1) {
            root                    = children[0];
            continue;
        }
        first                       = children[--count];
        while (count >0) {
            second                  = children[--count];
            compares++;
            if (COMPARE_LT(data[first], data[second])) {
               node[second].sibling = node[first].child;
               node[first].child    = second;
            } else {
               node[first].sibling  = node[second].child;
               node[second].child   = first;
               first                = second;
            }
        }
        root                        = first;
    }
/*
 *  Each node sibling field now contains the position index of
 *  the corresponding element of the data array.  In effect it
 *  is a permutation specifying the index to which each element 
 *  is to be moved.  We first invert the permutation, using the
 *  the child node to hold it.  The inverse is a permutation
 *  the index of where each elment is to be moved from.  Using
 *  the 'come from' permutation minimizes the number of required
 *  data moves for a reordering of the data in place.
 *  
 */
    for (i=n;   --i >= 0;) node[node[i].sibling].child = i;
    for (i=0;i<n;i++) {
        if (node[i].child <= i) continue;
        for (j=i, save=data[i];;) {
            k               = node[j].child;
            node[j].child   = PROCESSED;
            if (k == i)  {
                data[j]     = save;
                break;
            }
            data[j]         = data[k];
            j               = k;
        }
    }
    free (node);
    return compares;
}