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

  1. Split the list into two halves.
  2. Call recursive function mergeSort() two sort the individual lists.
  3. 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





Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.
Learn PCB Designing: PCB DESIGNING TUTORIAL




Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing » Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.