// Merge sort using circular linked list
// By Jason Hall <bo*******@yahoo.com>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
//#define debug
#define print_answer
//#define print_time
#define major_size 1048576
int mergesort(int *buffer, int size);
int merge(int *outbuffer, int *in1, int size1, int *in2, int size2);
struct merger
{
int size;
merger *next;
int *buffer;
};
int main(void)
{
int *buffer;
int i;
time_t seed, begin, end;
buffer=(int *) malloc(sizeof(int) *major_size);
time(&seed);
srand(seed);
for(i=0;i<major_size;i++)
{
//buffer[i]=rand()%100;
buffer[i]=major_size-i;
}
time(&begin);
mergesort(buffer, major_size);
time(&end);
#ifdef print_time
printf("Time is %i\n", end-begin);
#endif
#ifdef print_answer
for(i=0;i<major_size;i++)
{
printf("%i ", buffer[i]);
}
#endif
printf("\n");
free(buffer);
}
int mergesort(int *buffer, int size)
{
merger *first, *temp, *temp2;
int i, *tempbuffer, entnow, remain, sum, entries, x, *temp3;
#ifdef debug
int debugcount=2;
#endif
entnow=size/2;
remain=size%2;
sum=entnow+remain;
entries=entnow;
do
{
entnow=sum/2;
remain=sum%2;
sum=entnow+remain;
entries+=entnow;
}while(entnow!=1 || remain!=0);
if(size<=1)
{
return -1;
}
if(size==2)
{
if(buffer[0]>buffer[1])
{
x=buffer[1];
buffer[1]=buffer[0];
buffer[0]=x;
}
}
first=(merger *) malloc(sizeof(merger));
temp=first;
if(size%2==0)
{
for(i=0;i<size-2;i+=2)
{
tempbuffer=(int *) malloc(sizeof(int)*2);
merge(tempbuffer, buffer+i, 1, buffer+i+1, 1);
temp->buffer=tempbuffer;
temp->next=(merger *) malloc(sizeof(merger));
temp->size=2;
temp=temp->next;
}
tempbuffer=(int *) malloc(sizeof(int)*2);
merge(tempbuffer, buffer+size-2, 1, buffer+size-1, 1);
temp->buffer=tempbuffer;
temp->next=first;
temp->size=2;
}
else
{
for(i=0;i<size-1;i+=2)
{
tempbuffer=(int *) malloc(sizeof(int)*2);
merge(tempbuffer, buffer+i, 1, buffer+i+1, 1);
temp->buffer=tempbuffer;
temp->next=(merger *) malloc(sizeof(merger));
temp->size=2;
temp=temp->next;
//entries++;
}
tempbuffer=(int *) malloc(sizeof(int));
tempbuffer[0]=buffer[size-1];
temp->buffer=tempbuffer;
temp->next=first;
temp->size=1;
//entries++;
}
for(i=0;i<entries-3;i++)
{
tempbuffer=(int *) malloc(sizeof(int)*(temp->size+temp->next->size));
merge(tempbuffer, temp->buffer, temp->size, temp->next->buffer, temp->next->size);
temp->size=temp->size+temp->next->size;
free(temp->buffer);
free(temp->next->buffer);
temp->buffer=tempbuffer;
temp2=temp->next;
temp->next=temp->next->next;
free(temp2);
temp=temp->next;
entries--;
#ifdef debug
printf("Level %i\n", debugcount);
debugcount++;
#endif
}
merge(buffer, temp->buffer, temp->size, temp->next->buffer, temp->next->size);
#ifdef debug
printf("Level %i\n", debugcount);
#endif
free(temp->next->buffer);
free(temp->next);
free(temp->buffer);
free(temp);
}
int merge(int *outbuffer, int *in1, int size1, int *in2, int size2)
{
int i=0,j=0, k=0;
while(i<size1 && j<size2)
{
if(in1[i]<=in2[j])
{
outbuffer[k]=in1[i];
i++;
}
else
{
outbuffer[k]=in2[j];
j++;
}
k++;
}
if(i<size1)
{
while(i<size1)
{
outbuffer[k]=in1[i];
i++;
k++;
}
}
else
{
while(j<size2)
{
outbuffer[k]=in2[j];
j++;
k++;
}
}
return 0;
}
