/* A Fast Bubble sort algorithm for a list. This code has not been tested. */
/* This version sorts the list, instead of swapping the contents of the list. */

typedef struct list_T {
  struct list_T *next;
  void *contents;
} list_t;



void bsort(list, nr, comp)
list_t **list; int nr;
/* int (*comp)(const void *, const void *); */
int (*comp)();
{   int last,
        first;
    int d = nr / 2 + 1;

    /* Quick bubble sort: */
    while (d > 1)
    {   int nr_swapped = 0,
            i;
        list_t **l1 = list,
               **l2 = list;
        for (i = 0; i < d; i++)
            l2 = &(*l2)->next;

        last = nr - d;

        for (i = 0; i < last; i++, l1 = l1->next, l2 = l2->next)
            if (comp((*l1)->contents, (*l2)->contents) > 0)
            {   list *h;
	        h = *l1 ;
		*l1 = *l2 ;
		*l2 = h ;
		h = (*l1)->next ;
		(*l1)->next = (*l2)->next ;
		(*l2)->next = h ;
                nr_swapped++;
            }

        if  (nr_swapped == 0)
            d = d / 3;
        else
        {   double nd = (double)nr_swapped/(double)last;
            nd = (1 + sqrt(nd))/2;
            d = (int)( d * nd );
        }
        if (d < 1)
            d = 1;
    }

    /* Normale bubble-sort algorithme: */

    first = 0;
    last = nr - 1;
    while (first < last)
    {   int n_first,
            n_last,
            i;
        list_t **l1 = list;

        n_last = first;
        for (i = first; i < last; i++, l1 = l2, l2 = l2->next)
            if (comp((*l1)->contents, (*l1)->next->contents) > 0)
            {   list *h;
	        h = *l1 ;
		*l1 = h->next ;
		h->next = (*l1)->next ;
		(*l1)->next = h ;
                n_last = i;
            }
        last = n_last;

    }
}