Skip to main content

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
          

Comments

Popular posts from this blog

Tricky Questions or Puzzles in C ( Updated for 2026)

Updated for 2026 This article was originally written when C/C++ puzzles were commonly asked in interviews. While such language-specific puzzles are less frequent today, the problem-solving and logical reasoning skills tested here remain highly relevant for modern Software Engineering, Data Engineering, SQL, and system design interviews . Why These Puzzles Still Matter in 2026 Although most Software &   Data Engineering interviews today focus on Programming, SQL, data pipelines, cloud platforms, and system design , interviewers still care deeply about how you think . These puzzles test: Logical reasoning Edge-case handling Understanding of execution flow Ability to reason under pressure The language may change , but the thinking patterns do not . How These Skills Apply to Data Engineering Interviews The same skills tested by C/C++ puzzles appear in modern interviews as: SQL edge cases and NULL handling Data pipeline failure scenarios Incremental vs ...

The Vignere cipher

The Vignere cipher is a method of encryption which uses caesar cipher on each letter based on the letters of keyword.In caeser cipher each letter of the plaintext is shifted number of tomes depending upon the key value for examlple if the key=2 then the letter A is shifted two times and encrypted as C.Vignere cipher uses this technique on each of the letters but with different keys each time.That is the reason it appears unbreakable at first.But it is quite easy to understand and implement. For encrypting the plaintext vignere cipher uses vignere square or tabula recta which is like 26 X 26 table consisting of alphabets A-Z on ech row and columns.The columns in a table are such that each next column first alphabet is obtained by shifting previous column alphabet by one. Here is the figure of vignere square or tabular recta For the Encryption process the cipher uses different alphabets from the rows each time depending upon the alphabet key is having.So the process of encr...

Decorators in Python

Decorators provide additional functionality to the functions without directly changing their definition of them. Basically, it takes the functions as an argument, adds functionality to them, and returns it.  Before diving deep into the concept of Decorators, let's first try to understand  What are functions in Python and what is an inner function? In Python everything is Objects, be it Class, Variables, and Functions . So functions are python first-class objects that can be used or passed as an argument. You can store the functions in variables, you can pass a function to another function as parameters, and you can also return the function from the function. Below is one simple example where we are treating functions as objects . def make_me_lowercase ( str ): return str .lower() print (make_me_lowercase( "HELLO World" )) copy_of_you = make_me_lowercase print (copy_of_you( "HELLO World" )) The output of the above calls for both the functio...