# Merge Sort for Linked Lists

Posted in  Vinay Khatri
Last updated on September 28, 2023

There are a plethora of sorting algorithms present for arrays like the bubble sort, insertion sort, selection sort, heap sort, merge sort, quick sort, and many more. But in the case of Linked Lists, the implementation of all the sorting algorithms is difficult. Heapsort is totally impossible for sorting the linked list.

In this article, we will discuss how to apply the Merge Sort algorithm to sort the given linked list in ascending order.

Given a singly linked list containing n number of nodes, sort the linked list in the ascending order using the merge sort sorting algorithm. Inputs:

• 11-> 2 -> 4 -> 1 -> 9-> null
• 1 -> null

Outputs:

• 1 -> 2 -> 4 -> 9 -> 11 -> null
• 1 -> null

### Merge Sort Algorithm for Array’s data structure

• Check for the condition start<end.
• First of all, find the middle element of the array. Middle element is equal to the(start+(end-start)/2).
• Recursively call the array for 0(start) to mid element(end) and mid+1(start) to length-1 of the array until start < end .
• Call MergeSort (start ,mid ,end).
• In MergeSort Function, sort the two halves for the array.

The above algorithm is not suitable for the Linked List sorting because, in Linked List, we cannot access a particular node of the linked list in O(1). This is because of the non-contiguous memory allocation of the Linked List.

On the other hand, arrays have contiguous memory allocation. We can easily find the middle element but in the case of the linked list, we have to use another algorithm i.e the Tortoise-Hare Algorithm.

### TORTOISE-HARE Algorithm

• Iterate the Linked List using two pointers/references, one pointer is slow and the other pointer/reference is fast.
• Update the slow pointer/reference by one node and the fast pointer/reference by two nodes.
• Return the slow pointer/reference which is the middle node of the linked list.

The rest of the steps to perform the merge sort in the linked list are the same with very few variations.

### Approach

• Find the middle element of the Linked List using the TORTOISE-HARE algorithm.
• Divide the element into two halves head and middle.next position of the linked list.
• Recursively Divide the generated halves into another half till head or head.next becomes null.
• Merge the two halves by sorting each node’s data.

JAVA

``````//Importing Libraries
import java.util.*;
import java.io.*;
//Creating class Node
class Node{
int data; //Creating data element to be stored in the node of the linked list
Node  next;//Creating next reference of the node in the linked list
//Creating Constructor to initialize the data members
public Node(int data){
this.data=data;
this.next=null;
}
}
//Creating function to push the node a
static void push(int data){
//Checking the base condition
}
else{
//Creating temporary reference of the  head
while(temp.next!=null){
temp=temp.next;
}
//insert the node at the end of the linked  list
temp.next=new Node(data);
}

}
//Function to print the linked list
//Print the node value of the linked list
}
}
//Function to get the middle element of the given linked list
//Checking the base condition
}
//Creating two reference for the linked list
//Slow Reference
//Fast Reference
while(fast.next!=null && fast.next.next!=null){
//Update the slow pointer
slow=slow.next;
//Update the fast pointer
fast=fast.next.next;
}
//Return the slow reference that contains the middle element of the linked list
return slow;
}
//Function to sort the two halves of the linked list
static Node sortedMerge(Node left,Node right){
//Checking the base conditions
if(left==null){
return right;
}

if(right==null){
return left;
}
//Creating a temporary reference to refer to to the sorted linked list
Node result=null;
//Checking if the left reference data is smaller than the right reference data
if(left.data<=right.data){
//Update the result reference
result=left;
//Recursively call the left.next for next node
result.next=sortedMerge(left.next, right);
}
else{
//Update the result reference
result=right;
//Recursively call the left.next for next node
result.next=sortedMerge(left, right.next);
}
return result;

}
//Function to perform the merge sort of the linked list
//Checking the base conditions
}
//Getting the middle element
//Creating second half of the linked list
Node secondHalf=firsthalf.next;
//Break the middle element reference
firsthalf.next=null;

//Recursively call the two halves of the linked list
Node right=mergeSort(secondHalf);
//call for the sorting
Node sortedList=sortedMerge(left,right);
//Return the complete sorting linked list
return sortedList;

}
public static void main(String[] args) {
//Creating object of merge linked list
//Creating first node of the linked list
ob.push(15);
//Creating second  node of the linked list
ob.push(10);
//Creating third node of the linked list
ob.push(5);
//Creating fourth node of the linked list
ob.push(20);
//Creating fifth node of the linked list
ob.push(3);
//Creating sixth node of the linked list
ob.push(2);
//Creating new line
System.out.println();
//Call for sorting the linked list

}
}``````

Output: Python

``````#Creating Node class
class Node:
def __init__(self,data):
self.data=data #Creating data of the node
self.next=None #Creating next reference of the node of the linked list
def __init__(self):
#Function to push the node in the linked list

def push(self,data):
#Checking the base condition
#Creating First node of the linked list
else:
#Creating temporary reference of the linked list
while(temp.next is not None):
temp=temp.next
#Insert the node at the end of the linked list
temp.next=Node(data)
#Function to get the middle element of the linked list
#Checking the base condition
else:
#Creating two reference
#Slow Reference
#Fast Reference
while(fast.next !=None and fast.next.next!=None):
#Update the Fast Reference by two steps
fast=fast.next.next
#Update the slow Reference by one step
slow=slow.next
#Return the slow Reference

return slow
#Function to Perform the merge sort
#Checking the base condition
else:
#Storing the middle of the Linked list
#Creating Second part of the linked list
second=First.next
#Break the point of the first half to the second half
First.next=None
#Perform MergeSort on the First half
#Perform MergeSort on the Second half
right=self.MergeSort(second)
#Call function to sort the both halves
SortedList=self.sort(First,second)

return SortedList
#Function to sort the two halves of the linked list
def sort(self,first,second):
#Checking the base conditions
if(first is None):
return second
if(second is None):
return first
#Creating Result reference
Result=None
#Checking the  first node data of first part
if(first.data<=second.data):
Result=first
#Recursively call sort() Method again
Result.next=self.sort(first.next,second)
else:
Result=second
#Recursively call sort() Method again for next element
Result.next=self.sort(first,second.next)
return Result
#Function to print the linked list
#Creating reference of the linked list
list_=[]
while(temp is not None):
#Append the items of the linked list into the list_
list_.append(temp.data)
temp=temp.next
#Print the list
print(list_)
#Creating List reference of the Linked List
#Inserting node in the Single list
List.push(11)
List.push(2)
List.push(1)

Output: C++

``````//Importing all the required libraries
#include
#include
#include<bits/stdc++.h>
using namespace std;
//Creating structure for the node of linked list
struct Node{
int data;//data to be stored to the node in the linked list

Node*next;//next reference to the node in the linked list
//Creating Constructor
Node(int data){
this->data=data; //Storing the data to the node
this->next=nullptr;

}
};
//Function to Transverse the Linked list
//Checking if the Linked list is null or not
if(temp==NULL){
return;
}
while(temp!=NULL){
cout<data<<" "; temp=temp->next;
}

}
//Function to get the middle element of the given linked list
//Checking the base condition
}
//Creating two reference for the linked list
//Slow Reference
//Fast Reference
while(fast->next!=NULL && fast->next->next!=NULL){
//Update the slow pointer
slow=slow->next;
//Update the fast pointer
fast=fast->next->next;
}
//Return the slow reference that contains the middle element of the linked list
return slow;
}
//Function to sort the two halves of the linked list
Node* sortedMerge(Node *left,Node *right){
//Checking the base conditions
if(left==NULL){
return right;
}

if(right==NULL){
return left;
}
//Creating a temporary reference to refer the sorted linked list
Node *result=NULL;
//Checking if the left reference data is smaller than the right reference data
if(left->data<=right->data){
//Update the result reference
result=left;
//Recursively call the left.next for next node
result->next=sortedMerge(left->next, right);
}
else{
//Update the result reference
result=right;
//Recursively call the left.next for next node
result->next=sortedMerge(left, right->next);
}
return result;

}
//Function to perform the merge sort of the linked list
//Checking the base conditions
}
//Getting the middle element
//Creating second half of the linked list
Node *secondHalf=firsthalf->next;
//Break the middle element reference
firsthalf->next=NULL;

//Recursively call the two halves of the linked list
Node *right=mergeSort(secondHalf);
//call for the sorting
Node *sortedList=sortedMerge(left,right);
//Return the complete sorting linked list
return sortedList;

}

int main(){
//Creating Second node of the linked list
//Creating third node of the linked list
//Creating third node of the linked list

printf("\n");
printf("\n");

return 0;

}``````

Output: ### Complexity

• Time Complexity : The Time complexity of this approach is O(nlog(n).
• Space Complexity : The Space Complexity of this approach is O(1).

## Conclusion

Merge Sort for Linked Lists is one of the most interesting problems of Data structure. In this article, we have discussed an approach to sort a linked list using Merge Sort. Sorting of linked lists is a little bit difficult due to the non-contiguous memory location of the nodes available in the linked list. But with little variation of the naive merge sort algorithm, we can easily sort the linked list desired order.

We hope this article will help you to understand the problem statement and you will be able to solve any other variation of this problem.

Happy Coding!