#include<stdio.h>
#include<stdlib.h>
/* Link list node */
struct node
{
int data;
struct node* next;
};
void mergesort(struct node** head);
void merge(struct node **head, struct node **a, struct node **b);
void split(struct node **head, struct node **a,struct node **b);
void split(struct node **head, struct node **a,struct node **b)
{
/*i dont have to check if the list is empty or whether it has only one node in this function
because that condition has already been checked in the calling function*/
/*so i know for a fact that the list pointed to by head contains atleast 2 nodes*/
struct node *front=*head;
struct node *rear=(*head)->next;
while(rear!=NULL)
{
rear=rear->next;
if(rear!=NULL)
{
front=front->next;
rear=rear->next;
}
}
/*now front points to the end of the first list*/
*a=*head;
*b = front->next;
front->next = NULL;
}
void mergesort(struct node** head)
{
struct node *a = NULL;
struct node *b = NULL;
/*if list to be sorted is empty or contains only 1 element , then it is trivially sorted*/
if((*head==NULL)||((*head)->next == NULL))
{
return;
}
/*partition the list into 2 halves*/
split(head,&a,&b);
mergesort(&a);
mergesort(&b);
merge(head,&a,&b);
}
void merge(struct node **head, struct node **a, struct node **b)
{
struct node *x=*a;
struct node *y=*b;
struct node **s=NULL;
struct node *z=NULL;
/* x and y now point to the beginning of the 2 lists*/
if((x==NULL)&&(y==NULL)) /*if both lists are empty*/
{
*head = NULL;
return;
}
if((x==NULL)) /*if x is empty but y has elements*/
{
*head = y;
return;
}
if((y==NULL)) /*if y is empty but x has elements*/
{
*head = x;
return;
}
/*only other case remaining is that both list have elements*/
while((x!=NULL)&&(y!=NULL))
{
if(*s==NULL) /*adding first element to the unified list*/
{
*s = malloc(sizeof(struct node));
z = *s;
}
else
{
z->next = malloc(sizeof(struct node));
z = z->next;
}
if(x->data < y->data)
{
z->data = x->data;
x = x->next;
}
else if(x->data > y->data)
{
z->data = y->data;
y=y->next;
}
else if(x->data == y->data)
{
z->data = x->data;
x = x->next;
y = y->next;
}
}
/*now if one list got exhausted and the other remains*/
while(x!=NULL)
{
z->next = malloc(sizeof(struct node));
z = z->next;
z->data = x->data;
x = x->next;
}
while(y!=NULL)
{
z->next = malloc(sizeof(struct node));
z = z->next;
z->data = y->data;
y = y->next;
}
z->next = NULL;
*head = *s;
}
/* Function to print nodes in a given linked list */
void printList(struct node *node)
{
while(node!=NULL)
{
printf("%d ", node->data);
node = node->next;
}
}
/* Function to insert a node at the beginging of the linked list */
void push(struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Drier program to test above functions*/
int main()
{
/* Start with the empty list */
struct node* res = NULL;
struct node* p = NULL;
/* Let us create a unsorted linked lists to test the functions
Created lists shall be a: 2->3->20->5->10->15 */
push(&p, 15);
push(&p, 10);
push(&p, 5);
push(&p, 20);
push(&p, 3);
push(&p, 2);
/* Sort the above created Linked List */
mergesort(&p);
printf("\n Sorted Linked List is: \n");
printList(p);
getchar();
return 0;
}
hi this is the code i wrote to perform mergesort on link list, it’s not working and i am unable to find the bug. please help .