Program to perform Merge Sort using Linked list

Merge Sort is being done using Divide and Conquer Algorithm.We are going to use linked list for performing the merge sort.I will going to write the functions of the program and not the whole program.




Program :

/* This function takes the head of the linked list and declare two nodes a and b and then split the linked list by calling splitlinkedlist( ) function by passing head and two nodes and then sort recursively each part . */

struct node
{
int data;
struct node*next;
};
void mergesort(struct node *head1)
{
struct node *head=*head1;
struct node *a;
struct node *b;
if (head==NULL||head->next==NULL)
return;
splitlinkedlist(head,&a,&b);
mergesort(&a);                      // Recursively sort the splited nodes
mergesort(&b);
*head1=sort_merge(a,b);
}

/* This function is used to split the linked list from middle, for that we are taking a as a front node and b as back node and we are declaring two new node fast and slow,and then increment fast two times and slow one time such that the fast node reaches to the end and the slow node remain at the middle.Thus splitting the linked list */

void splitlinkedlist(struct node *source,struct node **front,struct node **back)
{
struct node*fast;
struct node*slow;
if(source==NULL||source->next==NULL)
{
*front=source;
*back=NULL;
}
else
{
slow=source;                       //Assign source to slow and fast as source->next
fast=source->next;
}
while(fast!=NULL)            // Iterate the loop till the end and increment fast and slow
{
fast=fast->next;
if(fast!=NULL)
{
fast=fast->next;
slow=slow->next;
}
}
*front=source;                     // Now assign source to front and back to slow->next and make it NULL
*back=slow->next;
slow->next=NULL;
}

/* This function is used to merge the sorted array again to get he final array.For that we define a new node result and compare the data of both nodes and copy the sorted array in the new linked list */

struct node *sort_merge(struct node *a,struct node *b)
{
struct node *result=NULL;
if(a==NULL)                 // If one is NULL return other
return b;
if(b==NULL)
return a;
if(a->data<=b->data)         // compare the data of two nodes and the one which is less is copied to result
{
result=a;
result->next=sort_merge(a->next,b);   // call recursively to merge the sorted array.
}
else
{
result=b;
result->next=sort_merge(a,b->next);
}
}

Also See:
Reverse a doubly linked list
How to reverse a linked list using recursion