/* A Fast Bubble sort algorithm. */

void bsort(arr, nr, size, comp)
void *arr; size_t nr, size;
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;
        char *arr1 = (char *)arr,
             *arr2 = (char *)arr + (long)d * size;
        last = nr - d;

        for (i = 0; i < last; i++, arr1 += size, arr2 += size)
            if (comp(arr1, arr2) > 0)
            {   swap(arr1, arr2, size);
                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 left/right bubble-sort algorithme: */

    first = 0;
    last = nr - 1;
    while (first < last)
    {   int n_first,
            n_last,
            i;
        char *arr1 = (char *)arr + (long)size * first,
             *arr2 = arr1 + size;

        n_last = first;
        for (i = first; i < last; i++, arr1 = arr2, arr2 += size)
            if (comp(arr1, arr2) > 0)
            {   swap(arr1, arr2, size);
                n_last = i;
            }
        last = n_last;

        if (first < last)
        {   arr2 = (char *)arr + (long)size * last;
            arr1 = arr2 - size;

            n_first = last;
            for (i = last; i > first; i--, arr2 = arr1, arr1 -= size)
                if (comp(arr1, arr2) > 0)
                {   swap(arr1, arr2, size);
                    n_first = i;
                }

            first = n_first;
        }
    }
}