448,527 Members | 949 Online
Need help? Post your question and get tips & solutions from a community of 448,527 IT Pros & Developers. It's quick & easy.

# Iterative Merge Sort Using Circular Linked List

 P: n/a // Merge sort using circular linked list // By Jason Hall #include #include #include #include //#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;ibuffer[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;ibuffer=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;ibuffer=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;isize+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