Home »
C++ programs
Merge sort for single linked lists
Merge sort for single linked list using C program: In this article, we are going to see how to sort two linked lists using merge sort?
Submitted by Radib Kar, on December 26, 2018
Problem statement: Write a C++ program to sort two single linked lists using merge sort technique.
Solution: Merge sort is an efficient technique for sorting linked lists using recursion.
Algorithm for merge sort
- Split the list into two halves.
- Call recursive function mergeSort() two sort the individual lists.
- Merge two sorted list.
1. Split the list into two halves
We use Floyd’s tortoise & hare algorithm for partitioning the linked list into two halves. We declare a slow pointer and a fast pointer. Slow pointer moves one step ahead where the fast pointer moves two step at a time. Thus when the fast pointer reaches the end of the list, the slow pointer is at the midway.
slow=head; //head of the list
fast=head->next;
while(fast!=NULL){
fast=fast->next;
if(fast!=NULL){
slow=slow->next;
fast=fast->next;
}
}
//split1 && split2 points to the head of the split list
*split1=head;
*split2=slow->next;
//split the list by partitioning
slow->next=NULL; //partitioning
2. Call recursive function mergeSort() two sort the individual lists
Let split1 & split2 points to the two individual list after partitioning.
We call mergeSort() recursively two sort this two list.
mergeSort(&split1);
mergeSort(&split2);
3. Merge two sorted list
Finally merge two sorted list into another sorted list.
We can do it by comparing elements of two list.
C++ implementation for Merge sort for single linked lists
#include<bits/stdc++.h>
using namespace std;
class node{
public:
int data; // data field
struct node *next;
};
void display(class node* head){
node* current=head; // current node set to head
while(current!=NULL){ //traverse until current node isn't NULL
printf("%d ",current->data);
current=current->next; // go to next node
}
}
node* creatnode(int d){
node* temp=(node*)malloc(sizeof(node));
temp->data=d;
temp->next=NULL;
return temp;
}
node* mergeList(node* split1,node* split2){
//merging two sorted list
node* newhead=NULL;
//base cases
if(split1==NULL)
return split2;
if(split2==NULL)
return split1;
//recursively merge
if(split1->data<=split2->data){
newhead=split1;
newhead->next=mergeList(split1->next,split2);
}
else{
newhead=split2;
newhead->next=mergeList(split1,split2->next);
}
return newhead;
}
void splitList(node* head,node** split1,node** split2){
//similar to flyod's tortoise algorithm
node* slow=head;
node* fast=head->next;
while(fast!=NULL){
fast=fast->next;
if(fast!=NULL){
slow=slow->next;
fast=fast->next;
}
}
*split1=head;
*split2=slow->next;
//spliting
slow->next=NULL;
}
void mergeSort(node** refToHead){
node* head=*refToHead;
node* split1,*split2;
//base case
if(head==NULL || head->next==NULL){
return;
}
//split the list in two halves
splitList(head,&split1,&split2);
//recursively sort the two halves
mergeSort(&split1);
mergeSort(&split2);
//merge two sorted list
*refToHead=mergeList(split1,split2);
return;
}
int main(){
printf("creating the linked list by inserting new nodes at the end\n");
printf("enter 0 to stop building the list, else enter any integer\n");
int k,count=1,x;
node* curr,*temp;
scanf("%d",&k);
node* head=creatnode(k); //buliding list, first node
scanf("%d",&k);
temp=head;
///////////////////inserting at the end//////////////////////
while(k){
curr=creatnode(k);
temp->next=curr;//appending each node
temp=temp->next;
scanf("%d",&k);
}
cout<<"before merge sort...\n";
display(head); // displaying the list
cout<<"\nafter merge sort...\n";
mergeSort(&head);
display(head);
return 0;
}
Output
creating the linked list by inserting new nodes at the end
enter 0 to stop building the list, else enter any integer
6 5 4 7 1 0
before merge sort...
6 5 4 7 1
after merge sort...
1 4 5 6 7
Example with explanation
Let the linked be
6->5->4->7->1->NULL
Head=6
----------------------------------------------------------------
mergeSort(6)
6 !=NULL
6->next !=NULL
Call to splitList(6,split1,split2)
----------------------------------------------------------------
In splitList(6,split1,split2):
slow=6
fast=6->next=5
iteration 0:
5!=NULL
fast=5->next=4
4!=NULL
slow=6->next=5
fast=4->next=7
iteration 1:
7!=NULL
fast=7->next=1
1!=NULL
slow=5->next=4
fast=1->next=NULL
iteration 2:
fast==NULL
so iteration stops
split1=6(head)
split2=slow->next=4->next=7
slow->next=NULL
thus the partitioned linked lists are
split1=6->5->4->NULL
split2=7->1->NULL
----------------------------------------------------------------
Now we individually sort split1 & split2 recursively
Thus needless to say it again partitions
both the list until base cases is reached.
The ultimate outcome is the two sorted list
Split1 pointing to 4->5->6->NULL
Split2 pointing to 1->7->NULL
----------------------------------------------------------------
Now we merge this two sorted list to produce the ultimate sorted list
mergeList(split1, split2) // mergeList(4, 1)
Split1!=NULL
Split2!=NULL
Split1->data>split2->data (4>1)
Thus newhead =split2 // newhead =1
newhead->next=mergeList(split1, split2->next));
Call mergeList(split1, split2->next) // (4, 7)
----------------------------------------------------------------
mergeList( split1, split2) //mergeList(4,7)
Split1!=NULL
Split2!=NULL
Split1->data<split2->data (4<7)
Thus newhead =split1 // newhead =4
newhead->next=mergeList(split1->next, split2));
Call mergeList(split1->next, split2) // (5, 7)
----------------------------------------------------------------
mergeList( split1, split2) //mergeList(5,7)
Split1!=NULL
Split2!=NULL
Split1->data<split2->data (5<7)
Thus newhead =split1 // newhead =5
newhead->next=mergeList(split1->next, split2));
Call mergeList(split1->next, split2) // (6, 7)
----------------------------------------------------------------
mergeList( split1, split2) //mergeList(6,7)
Split1!=NULL
Split2!=NULL
Split1->data<split2->data (6<7)
Thus newhead =split1 // newhead =6
newhead->next=mergeList(split1->next, split2));
Call mergeList(split1->next, split2) // (NULL, 7)
----------------------------------------------------------------
mergeList( split1, split2) //mergeList(5,7)
Split1==NULL
Return split2 (7->NULL)
----------------------------------------------------------------
Thus at mergeList(6,7)
newhead=6
newhead->next=7->NULL
function returns 6->7->NULL
----------------------------------------------------------------
Thus at mergeList(5,7)
newhead=5
newhead->next=6->7->NULL
function returns 5->6->7->NULL
----------------------------------------------------------------
Thus at mergeList(4,7)
newhead=4
newhead->next=5->6->7->NULL
function returns 4->5->6->7->NULL
----------------------------------------------------------------
Thus at mergeList(4,1)
newhead=1
newhead->next=4->5->6->7->NULL
function returns 1->4->5->6->7->NULL
Which is the sorted list