#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

void scal(int, int, int, int [], int []);
void bin(int, int [], int []);

int main()
{

    int a[50],b[50];
    srand(time(NULL));

    int i;
    for(i=0;i<50;i++)
    {
        a[i]=rand()%301;
    }
    bin(50,a,b);
    for(i=0;i<50;i++)
    {
        printf("%d\n",b[i]);
    }


    return 0;
}


void bin(int n, int a[], int b[])
{
    int i,k=0,p=0;
    i=1;
    while(i<n)
    {
        k=1;
        while(k<n)
        {
            if(k+2*i-1<=n) p=k+2*i-1;
            else if (k+i<=n) p=n;
            else p=0;

            if(p>0)
            {
                scal(k,i,p,a,b);
                k=k+i+i;
            }
        }
        i=2*i;
    }
}




void scal(int l, int s, int p, int a[], int b[])
{
    int l1,p1,i;
    l1=l;
    p1=s+1;
    i=l;

    while(l1<s && p1<p)
    {
        if(a[l1]>a[p1])
        {
            b[i]=a[p1];
            p1++;
        }
        else
        {
            b[i]=a[l1];
            l1++;
        }
        i++;
    }

    while(l1<s)
    {
        b[i]=a[l1];
        i++;
        l1++;
    }

    while(p1<p)
    {
        b[i]=a[p1];
        i++;
        p1++;
    }
    i=l;
    while(i<p)
    {
        a[i]=b[i];
        i++;
    }
}