Iterative Merge Sort Using Circular Linked List

[Booser]

// Merge sort using circular linked list

// By Jason Hall <[email protected]>

#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=rand()%100;
buffer=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);
}
#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<=in2[j])
{
outbuffer[k]=in1;
i++;
}
else
{
outbuffer[k]=in2[j];
j++;
}
k++;
}
if(i<size1)
{
while(i<size1)
{
outbuffer[k]=in1;
i++;
k++;
}
}
else
{
while(j<size2)
{
outbuffer[k]=in2[j];
j++;
k++;
}
}


return 0;
}

 

[CBFalconer]

// Merge sort using circular linked list

// By Jason Hall <[email protected]>

Seems somewhat long to me. Try this, lists need not be circular.

/* List handling, reversal, sort, merge, split */
/* file listops.h */
/* By C.B. Falconer. Public Domain, use as you wish */
/* Attribution appreciated. */
/* ================== 30 April, 2001 ================== */

#ifndef listops_h_
#define listops_h_

#include <stddef.h> /* NULL */
#include <iso646.h> /* not, and */

/* The bare minimum to form a linked list */
typedef struct node {
struct node *next;
void *data;
} node, *nodeptr;

/* ======================================================= */
/* believed necessary and sufficient for NULL terminations */
/* Reverse a singly linked list. Reentrant (pure) code */
nodeptr revlist(nodeptr root);

/* ======================================================= */
/* split list p into 2 nearly equal lists, return 2nd part */
nodeptr splitlist(nodeptr p);

/* ================================ */
/* Merge two ordered lists into one */
nodeptr mergelists(nodeptr p1, nodeptr p2,
int (*cmp)(void *, void*)); /* compare */

/* ================================================== */
/* Recursively sort a linked list. The sort is stable */
/* This is an O(NlogN) process for all lists. */
nodeptr mergesort(nodeptr root,
int (*cmp)(void *, void*)); /* compare */

#endif

/* end listops.h */

/* List handling, reversal, sort, merge, split */
/* file listops.c */
/* By C.B. Falconer. Public Domain, use as you wish */
/* Attribution appreciated. */
/* ================== 30 April, 2001 ================== */

#include "listops.h"

/* ======================================================= */
/* believed necessary and sufficient for NULL terminations */
/* Reverse a singly linked list. Reentrant (pure) code */
nodeptr revlist(nodeptr root)
{
nodeptr curr, nxt;

if (root) { /* non-empty list */
curr = root->next;
root->next = NULL; /* terminate new list */
while (curr) {
nxt = curr->next; /* save for walk */
curr->next = root; /* relink */
root = curr; /* save for next relink */
curr = nxt; /* walk onward */
}
}
/* else empty list is its own reverse; */
return root;
} /* revlist */

/* ======================================================= */
/* split list p into 2 nearly equal lists, return 2nd part */
nodeptr splitlist(nodeptr p)
{
nodeptr p1, p2, p3;

p1 = p2 = p3 = p;
if (not p) return NULL;
do {
p3 = p2;
p2 = p2->next; /* advance 1 */
p1 = p1->next;
if (p1) p1 = p1->next; /* advance 2 */
} while (p1);

/* now form new list after p2 */
p3->next = NULL; /* terminate 1st half */
return p2;
} /* splitlist */

/* ================================ */
/* Merge two ordered lists into one */
nodeptr mergelists(nodeptr p1, nodeptr p2,
int (*cmp)(void *, void*)) /* compare */
{
node n;
nodeptr p;

p = &n;
n.next = p;

while (p1 and p2) {
if (cmp(p1, p2) <= 0) {
p->next = p1; p = p1; p1 = p1->next;
}
else {
p->next = p2; p = p2; p2 = p2->next;
}
}
/* at least one list now empty, copy other */
/* one or both of these operations is null */
if (p1) p->next = p1;
if (p2) p->next = p2;

/* check for empty lists */
if (n.next == &n) return NULL;
return n.next;
} /* mergelists */

/* ================================================== */
/* Recursively sort a linked list. The sort is stable */
/* This is an O(NlogN) process for all lists. */
nodeptr mergesort(nodeptr root,
int (*cmp)(void *, void*)) /* compare */
{
nodeptr p;

if (root and root->next) { /* 2 up items in list */
p = splitlist(root); /* alters list root */
root = mergelists(mergesort(root, cmp),
mergesort( p, cmp),
cmp);
}
/* else the unit or empty list is already sorted */

return root;
} /* mergesort */

/* end listops.c */