# Merge sort for single linked lists

Merge sort for single linked list in C++: In this tutorial, we will learn how to implement merge sort for single linked lists using a C++ program? By Radib Kar Last updated : August 01, 2023

## 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. The following are the steps/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

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
*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;
};

{
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 {
}

}

void splitList(node* head, node** split1, node** split2)
{
//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
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
----------------------------------------------------------------

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
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)
Call  mergeList(split1, split2->next) // (4, 7)
----------------------------------------------------------------

mergeList( split1, split2) //mergeList(4,7)
Split1!=NULL
Split2!=NULL
Split1->data<split2->data (4<7)
Call  mergeList(split1->next, split2) // (5, 7)
----------------------------------------------------------------

mergeList( split1, split2) //mergeList(5,7)
Split1!=NULL
Split2!=NULL
Split1->data<split2->data (5<7)
Call  mergeList(split1->next, split2) // (6, 7)
----------------------------------------------------------------

mergeList( split1, split2) //mergeList(6,7)
Split1!=NULL
Split2!=NULL
Split1->data<split2->data (6<7)
Call  mergeList(split1->next, split2) // (NULL, 7)
----------------------------------------------------------------

mergeList( split1, split2) //mergeList(5,7)
Split1==NULL
Return split2 (7->NULL)
----------------------------------------------------------------

Thus at mergeList(6,7)
function returns 6->7->NULL
----------------------------------------------------------------

Thus at mergeList(5,7)
function returns 5->6->7->NULL
----------------------------------------------------------------

Thus at mergeList(4,7)
function returns 4->5->6->7->NULL
----------------------------------------------------------------

Thus at mergeList(4,1)
function returns 1->4->5->6->7->NULL
Which is the sorted list
```