Home >>Cpp Programs >Merge sort singly linked list c++

# Merge sort singly linked list c++

### Merge sort singly linked list c++

In this example, we will see a C++ program through which we can implement the merge sort for a single linked list.

Algorithm:
• STEP 1: Split the list into two halves.
• STEP 2: Call recursive function mergeSort() two sort the individual lists.
• STEP 3: Merge two sorted list.
Program:
``````
#include <bits/stdc++.h>
using namespace std;
class node{
public:
int data; // data field
struct node *next;
};
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
//base cases
if(split1==NULL)
return split2;
if(split2==NULL)
return split1;
//recursively merge
if(split1->data<=split2->data){
}
else{
}
}
//similar to flyod's tortoise algorithm
while(fast!=NULL){
fast=fast->next;
if(fast!=NULL){
slow=slow->next;
fast=fast->next;
}
}
*split2=slow->next;
//spliting
slow->next=NULL;
}
node* split1,*split2;
//base case
return;
}
//split the list in two halves
//recursively sort the two halves
mergeSort(&split1);
mergeSort(&split2);
//merge two sorted list
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);
///////////////////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";
cout<<"\nafter merge sort...\n";
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
84 62 6 9 2 84 27 47 28 25 84 26 19 38 53 47 32 859 26 93 0
before merge sort...
84 62 6 9 2 84 27 47 28 25 84 26 19 38 53 47 32 859 26 93
after merge sort...
2 6 9 19 25 26 26 27 28 32 38 47 47 53 62 84 84 84 93 859