#include <math.h>

#define STYPE  double

void bsort(arr, nr)
STYPE *arr; int nr;
{   int last,
        first;
    int d = nr / 2 + 1;

    /* Quick bubble sort: */
    while (d > 1)
    {   int nr_swapped = 0,
            i;
        STYPE *arr1 = arr,
              *arr2 = arr + d;
        last = nr - d;
 
        for (i = 0; i < last; i++, arr1++, arr2++)
            if (*arr1 > *arr2)
            {   STYPE h = *arr1;
                *arr1 = *arr2;
                *arr2 = 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 left/right bubble-sort algorithme: */

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

        n_last = first;
        for (i = first; i < last; i++, arr1 = arr2, arr2++)
            if (*arr1 > *arr2)
            {   STYPE h = *arr1;
                *arr1 = *arr2;
                *arr2 = h;
                n_last = i;
            }
        last = n_last;

        if (first < last)
        {   arr2 = arr + last;
            arr1 = arr2 - 1;

            n_first = last;
            for (i = last; i > first; i--, arr2 = arr1, arr1--)
                if (*arr1 > *arr2)
                {   STYPE h = *arr1;
                    *arr1 = *arr2;
                    *arr2 = h;
                    n_first = i;
                }

            first = n_first;
        }
    }
}