Smoothsort

//C program for
//Sort the words elements by using smoothsort
#include <stdio.h>

#include <string.h>

struct state
{
	const char **record;
	size_t q, r, p, b, c, r1, b1, c1;
};
//Compare two string elements
int compare(const char *a , const char *b)
{
	return strcmp(a, b);
}
void up(size_t *a, size_t *b)
{
	size_t temp;
	temp = *a;*a += *b + 1;*b = temp;
}
void down(size_t *a, size_t *b)
{
	size_t temp;
	temp = *b;*b = *a - *b - 1;*a = temp;
}
void sift(struct state *s)
{
	int r0 = s->r1;
	int r2 = 0;
	const char *temp = s->record[r0];
	while (s->b1 > 2)
	{
		r2 = s->r1 - s->b1 + s->c1;
		if (compare(s->record[s->r1 - 1], s->record[r2]) >= 0)
		{
			r2 = s->r1 - 1;
			down( & s->b1, & s->c1);
		}
		if (compare(s->record[r2], temp) < 0)
		{
			s->b1 = 1;
		}
		else
		{
			s->record[s->r1] = s->record[r2];
			s->r1 = r2;
			down( & s->b1, & s->c1);
		}
	}
	if (s->r1 - r0 > 0)
	{
		s->record[s->r1] = temp;
	}
}
void trinkle(struct state *s)
{
	int p1 = s->p;
	int r0 = s->r1;
	int r2 = 0;
	int r3 = 0;
	const char *temp = s->record[r0];
	s->b1 = s->b;
	s->c1 = s->c;
	while (p1 > 0)
	{
		while ((p1 & 1) == 0)
		{
			p1 >>= 1;
			up( & s->b1, & s->c1);
		}
		r3 = s->r1 - s->b1;
		if (p1 == 1 || compare(s->record[r3], temp) < 0)
		{
			p1 = 0;
		}
		else
		{
			p1--;
			if (s->b1 == 1)
			{
				s->record[s->r1] = s->record[r3];
				s->r1 = r3;
			}
			else if (s->b1 >= 3)
			{
				r2 = s->r1 - s->b1 + s->c1;
				if (compare(s->record[s->r1 - 1], s->record[r2]) >= 0)
				{
					r2 = s->r1 - 1;
					down( & s->b1, & s->c1);
					p1 <<= 1;
				}
				if (compare(s->record[r2], s->record[r3]) < 0)
				{
					s->record[s->r1] = s->record[r3];
					s->r1 = r3;
				}
				else
				{
					s->record[s->r1] = s->record[r2];
					s->r1 = r2;
					down( & s->b1, & s->c1);
					p1 = 0;
				}
			}
		}
	}
	if (s->r1 - r0 != 0)
	{
		s->record[s->r1] = temp;
	}
	sift(s);
}
void semi_trinkle(struct state *s)
{
	const char *temp;
	s->r1 = s->r - s->c;
	if (compare(s->record[s->r1], s->record[s->r]) >= 0)
	{
		temp = s->record[s->r];
		s->record[s->r] = s->record[s->r1];
		s->record[s->r1] = temp;
		trinkle(s);
	}
}
void smooth_sort(const char **a, int size)
{
	struct state s;
	//set initial values
	s.record = a;
	s.r = 0;
	s.p = 1;
	s.b = 1;
	s.c = 1;
	int temp = 0;
	int work = 1;
	//Build tree 
	for (s.q = 1; s.q < size; s.q++)
	{
		s.r1 = s.r;
		if ((s.p & 7) == 3)
		{
			s.b1 = s.b;
			s.c1 = s.c;
			sift( & s);
			s.p = (s.p + 1) >> 2;
			/*Two "up"s, saves us a little time */
			temp = s.b + s.c + 1;
			s.b += temp + 1;
			s.c = temp;
		}
		else if ((s.p & 3) == 1)
		{
			if (s.q + s.c < size)
			{
				s.b1 = s.b;
				s.c1 = s.c;
				sift( & s);
			}
			else
			{
				trinkle( & s);
			}
			work = 1;
			while (work == 1)
			{
				work = 0;
				down( & s.b, & s.c);
				s.p <<= 1;
				if (s.b > 1)
				{
					work = 1;
				}
			}
			s.p++;
		}
		s.r++;
	}
	s.r1 = s.r;
	trinkle( & s);
	//Build sorted array 
	while (s.q--> 1)
	{
		if (s.b == 1)
		{
			s.r--;
			s.p--;
			while ((s.p & 1) == 0)
			{
				s.p >>= 1;
				up( & s.b, & s.c);
			}
		}
		else if (s.b > 2)
		{
			s.p--;
			s.r = s.r - s.b + s.c;
			if (s.p > 0)
			{
				semi_trinkle( & s);
			}
			down( & s.b, & s.c);
			s.p = (s.p << 1) + 1;
			s.r += s.c;
			semi_trinkle( & s);
			down( & s.b, & s.c);
			s.p = (s.p << 1) + 1;
		}
	}
}
//This are display the elements of given collection 
void display(const char *collection[], int size)
{
	int i = 0;
	for (i = 0; i < size; ++i)
	{
		//Display elements
		printf("%s\n", collection[i]);
	}
}
int main()
{
	//Define the string word
	const char *collection[] = {
		"time" , "life" , "dear" , "zero" , "moon" , "crazy" , "approach" , "code" , "today" , "sun" , "date"
	};
	//Get the size of unsorted elements
	int size = sizeof(collection) / sizeof(collection[0]);
	printf("Before Sort : \n");
	display(collection, size);
	//Perform the smooth sort
	smooth_sort(collection, size);
	printf("\nAfter Sort : \n");
	display(collection, size);
	return 0;
}

Output

Before Sort :
time
life
dear
zero
moon
crazy
approach
code
today
sun
date

After Sort :
approach
code
crazy
date
dear
life
moon
sun
time
today
zero