image source;
source.open("grey.bmp"); // https://dotink.co/img/quick-grey.png

int n = source.width;
int height = 1708;

image result;
result.open("bsort.png");
result.new(n, height);

for x from 0 to n
{
    result.setColor(x, 0, source.getColor(x, 0));
    result.setColor(x, 1, source.getColor(x, 0));
}

int y = 1;

int d = n / 2 + 1;

int direction = 1;

int nr_swapped = 1;
while (nr_swapped == 0 || d > 1)
{   
    nr_swapped = 0;

    int i = direction > 0 ? 0 : n - d - 1;
    while (0 <= i && i+d < n)
    {
        color col1 = result.getColor(i, y);
        color col2 = result.getColor(i+d, y);
        if (col1.r > col2.r)
        {
            nr_swapped++;
            result.setColor(i, y, col2);
            result.setColor(i+d, y, col1);
            if (y < height)
            {
                y++;
                for x from 0 to n
                    result.setColor(x, y, result.getColor(x, y-1));
            }
        }
        i += direction;
    }
    if  (nr_swapped == 0)
        d = d / 3;
    else
    {   double nd = (nr_swapped*1.0)/(n-d);
        nd = (1 + sqrt(nd))/2;
        d = floor( d * nd );
    }
    if (d < 1)
        d = 1;
    direction = 0 - direction;
}