Sort a linked list using merge sort

Given a linked list containing integer values, the goal is to sort the linked list in ascending order using the Merge Sort algorithm. For example, given the linked list: 9 -> 5 -> 7 -> 11 -> 3 -> 13 -> 4 -> 8 -> 2, after applying the Merge Sort algorithm, the linked list becomes: 2 -> 3 -> 4 -> 5 -> 7 -> 8 -> 9 -> 11 -> 13.

Merge Sort is a popular sorting algorithm known for its stability and consistent performance in both average and worst cases.

Idea to Solve the Problem

The Merge Sort algorithm follows a divide-and-conquer approach to sort a linked list. It involves recursively dividing the linked list into smaller sublists, sorting those sublists, and then merging the sorted sublists to produce the final sorted linked list.

Pseudocode

``````insert(head, value):
Create a new node with data = value
Else, traverse the list and add the new node at the end

Traverse the linked list and print each node's data

Initialize low and high pointers to head
While high is not NULL and high's next and next's next are not NULL and high's next is not tail and head's next's next is not tail:
Move low to next node
Move high to next node's next
Return low

merge_list(list1, list2):
If list1 is NULL, return list2
If list2 is NULL, return list1
Initialize result, tail, and node to NULL
Merge elements of list1 and list2 in sorted order
Return result

merge_sort(front, tail):
If front is NULL, front is tail, or front's next is NULL, return front
Find the middle node between front and tail
Get the right sublist by recursively calling merge_sort on middle's next to tail
Separate the linked list by setting middle's next to NULL
Get the left sublist by recursively calling merge_sort on front to middle
Merge the left and right sublists using merge_list
Return the merged list

main():
Insert elements into the linked list
Print "Before Sort"
Sort the linked list using merge_sort
Print "After Sort"

Algorithm Explanation

1. The `insert` function adds a new node with a given value at the end of the linked list.
2. The `display` function traverses the linked list and prints each node's data.
3. The `find_middle` function returns the middle node between the `head` and `tail` nodes.
4. The `merge_list` function merges two sorted linked lists and returns the merged result.
5. The `merge_sort` function recursively divides the linked list into sublists, sorts them, and merges the sorted sublists using the `merge_list` function.
6. In the `main` function, initialize the `head` of the linked list, insert elements into the linked list, display the linked list before sorting, apply the `merge_sort` function to sort the linked list, and display the linked list after sorting.

Code Solution

``````// C Program
// Sort a linked list using merge sort

#include <stdio.h>
//for malloc function
#include <stdlib.h>

//Create structure
struct Node
{
int data;
struct Node *next;
};
void insert(struct Node **head, int value)
{
//Create dynamic node
struct Node *node = (struct Node *) malloc(sizeof(struct Node));
if (node == NULL)
{
printf("Memory overflow\n");
}
else
{
node->data = value;
node->next = NULL;
{
}
else
{
//find last node
while (temp->next != NULL)
{
temp = temp->next;
}
temp->next = node;
}
}
}
{
{
return;
}
while (temp != NULL)
{
printf("  %d", temp->data);
temp = temp->next;
{
printf("Loop");
//When loop existing
return;
}
}
}
//This are returning middle node of given linked list
struct Node *find_middle(struct Node *head, struct Node *tail)
{
{
}
else
{
//Auxiliary variables
while (high != NULL && high->next != NULL && high->next->next != NULL && high->next != tail && head->next->next != tail)
{
//visit to next node
low = low->next;
//visit to second next node
high = high->next->next;
}
//This is middle element
return low;
}
}
//Merge two sorted list and return its result
struct Node *merge_list(struct Node *list1, struct Node *list2)
{
if (list1 == NULL)
{
//When list1 is empty
return list2;
}
else if (list2 == NULL)
{
return list1;
}
else
{
//Some auxiliary variables
struct Node *result = NULL;
struct Node *tail = NULL;
struct Node *node = NULL;
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1 != NULL || list2 != NULL)
{
if (list1 != NULL && list2 != NULL)
{
//When both list contain nodes
if (list1->data < list2->data)
{
//When first list element are smallest
node = list1;
list1 = list1->next;
}
else
{
//When second list element are smallest
node = list2;
list2 = list2->next;
}
}
else if (list1 != NULL)
{
//When first list contain element
//Get sublist
node = list1;
//Set that list1 empty
list1 = NULL;
}
else
{
//When second list contain element
//get sublist
node = list2;
list2 = NULL;
}
if (result == NULL)
{
//When get first node of resultant list
result = node;
}
else
{
//Add node at end of resultant list
tail->next = node;
}
tail = node;
}
return result;
}
}
//Perform merge sort in given linked list
struct Node *merge_sort(struct Node *front, struct Node *tail)
{
if (front == NULL || front == tail || front->next == NULL)
{
//When have zero or one node
return front;
}
//Find the relative middle node
struct Node *middle = find_middle(front, tail);
//Get the right side sublist
struct Node *right_nodes = merge_sort(middle->next, tail);
middle->next = NULL;
//Get the left side sublist
struct Node *left_nodes = merge_sort(front, middle);
//sorted merge in two list
return merge_list(left_nodes, right_nodes);
}
int main()
{
printf("\n Before Sort ");
printf("\n After Sort ");
return 0;
}``````

Output

`````` Before Sort
Linked List :  9  5  7  11  3  13  4  8  2
After Sort
Linked List :  2  3  4  5  7  8  9  11  13``````
``````// Java Program
// Sort a linked list using merge sort

class Node
{
public int data;
public Node next;
public Node(int data)
{
//set node value
this.data = data;
this.next = null;
}
}
{
public Node tail;
//Class constructors
{
this.tail = null;
}
//insert node at last of linke list
public void insert(int value)
{
//Create a node
Node node = new Node(value);
{
this.tail = node;
}
else
{
this.tail.next = node;
this.tail = node;
}
}
public void display()
{
{
while (temp != null)
{
System.out.print(" " + temp.data);
temp = temp.next;
{
//avoid loop
return;
}
}
}
else
{
}
}
//This are returning middle node of given linked list
public Node find_middle(Node first, Node last)
{
if (first.next == null || first == last)
{
return first;
}
else
{
//Auxiliary variables
//Get first node of linked list
Node low = first;
Node high = first;
while (high != null && high.next != null && high.next.next != null && high.next != last && head.next.next != last)
{
//visit to next node
low = low.next;
//visit to second next node
high = high.next.next;
}
//This is middle element
return low;
}
}
//Merge two sorted list and return its result
public Node merge_list(Node list1, Node list2)
{
if (list1 == null)
{
//When list1 is empty
return list2;
}
else if (list2 == null)
{
return list1;
}
else
{
//Some auxiliary variables
Node result = null;
Node tail = null;
Node node = null;
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1 != null || list2 != null)
{
if (list1 != null && list2 != null)
{
//When both list contain nodes
if (list1.data < list2.data)
{
//When first list element are smallest
node = list1;
list1 = list1.next;
}
else
{
//When second list element are smallest
node = list2;
list2 = list2.next;
}
}
else if (list1 != null)
{
//When first list contain element
//Get sublist
node = list1;
//Set that list1 empty
list1 = null;
}
else
{
//When second list contain element
//get sublist
node = list2;
list2 = null;
}
if (result == null)
{
//When get first node of resultant list
result = node;
}
else
{
//Add node at end of resultant list
tail.next = node;
}
tail = node;
}
return result;
}
}
//Perform merge sort in given linked list
public Node merge_sort(Node first, Node last)
{
if (first == null || first == last || first.next == null)
{
//When have zero or one node
return first;
}
//Find the relative middle node
Node middle = find_middle(first, last);
//Get the right side sublist
Node right_nodes = merge_sort(middle.next, last);
middle.next = null;
//Get the left side sublist
Node left_nodes = merge_sort(first, middle);
//sorted merge in two list
return merge_list(left_nodes, right_nodes);
}
public static void main(String[] args)
{
obj.insert(9);
obj.insert(5);
obj.insert(7);
obj.insert(11);
obj.insert(3);
obj.insert(13);
obj.insert(4);
obj.insert(8);
obj.insert(2);
System.out.print("\n Before Sort ");
obj.display();
System.out.print("\n After Sort ");
obj.display();
}
}``````

Output

`````` Before Sort
Linked List : 9 5 7 11 3 13 4 8 2
After Sort
Linked List : 2 3 4 5 7 8 9 11 13``````
``````//Include header file
#include <iostream>

using namespace std;

// C++ Program
// Sort a linked list using merge sort

class Node
{
public: int data;
Node * next;
Node(int data)
{
//set node value
this->data = data;
this->next = NULL;
}
};
{
Node * tail;
//Class constructors
{
this->tail = NULL;
}
//insert node at last of linke list
void insert(int value)
{
//Create a node
Node * node = new Node(value);
{
this->tail = node;
}
else
{
this->tail->next = node;
this->tail = node;
}
}
void display()
{
{
cout << "\n Linked List :";
while (temp != NULL)
{
cout << " " << temp->data;
temp = temp->next;
{
//avoid loop
return;
}
}
}
else
{
}
}
//This are returning middle node of given linked list
Node * find_middle(Node * first, Node * last)
{
if (first->next == NULL || first == last)
{
return first;
}
else
{
//Auxiliary variables
//Get first node of linked list
Node * low = first;
Node * high = first;
while (high != NULL && high->next != NULL && high->next->next != NULL && high->next != last && this->head->next->next != last)
{
//visit to next node
low = low->next;
//visit to second next node
high = high->next->next;
}
//This is middle element
return low;
}
}
//Merge two sorted list and return its result
Node * merge_list(Node * list1, Node * list2)
{
if (list1 == NULL)
{
//When list1 is empty
return list2;
}
else if (list2 == NULL)
{
return list1;
}
else
{
//Some auxiliary variables
Node * result = NULL;
Node * tail = NULL;
Node * node = NULL;
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1 != NULL || list2 != NULL)
{
if (list1 != NULL && list2 != NULL)
{
//When both list contain nodes
if (list1->data < list2->data)
{
//When first list element are smallest
node = list1;
list1 = list1->next;
}
else
{
//When second list element are smallest
node = list2;
list2 = list2->next;
}
}
else if (list1 != NULL)
{
//When first list contain element
//Get sublist
node = list1;
//Set that list1 empty
list1 = NULL;
}
else
{
//When second list contain element
//get sublist
node = list2;
list2 = NULL;
}
if (result == NULL)
{
//When get first node of resultant list
result = node;
}
else
{
//Add node at end of resultant list
tail->next = node;
}
tail = node;
}
return result;
}
}
//Perform merge sort in given linked list
Node * merge_sort(Node * first, Node * last)
{
if (first == NULL || first == last || first->next == NULL)
{
//When have zero or one node
return first;
}
//Find the relative middle node
Node * middle = this->find_middle(first, last);
//Get the right side sublist
Node * right_nodes = this->merge_sort(middle->next, last);
middle->next = NULL;
//Get the left side sublist
Node * left_nodes = this->merge_sort(first, middle);
//sorted merge in two list
return this->merge_list(left_nodes, right_nodes);
}
};
int main()
{
obj.insert(9);
obj.insert(5);
obj.insert(7);
obj.insert(11);
obj.insert(3);
obj.insert(13);
obj.insert(4);
obj.insert(8);
obj.insert(2);
cout << "\n Before Sort ";
obj.display();
cout << "\n After Sort ";
obj.display();
return 0;
}``````

Output

`````` Before Sort
Linked List : 9 5 7 11 3 13 4 8 2
After Sort
Linked List : 2 3 4 5 7 8 9 11 13``````
``````//Include namespace system
using System;

// C# Program
// Sort a linked list using merge sort

class Node
{
public int data;
public Node next;
public Node(int data)
{
//set node value
this.data = data;
this.next = null;
}
}
{
public Node tail;
//Class constructors
{
this.tail = null;
}
//insert node at last of linke list
public void insert(int value)
{
//Create a node
Node node = new Node(value);
{
this.tail = node;
}
else
{
this.tail.next = node;
this.tail = node;
}
}
public void display()
{
{
while (temp != null)
{
Console.Write(" " + temp.data);
temp = temp.next;
{
//avoid loop
return;
}
}
}
else
{
}
}
//This are returning middle node of given linked list
public Node find_middle(Node first, Node last)
{
if (first.next == null || first == last)
{
return first;
}
else
{
//Auxiliary variables
//Get first node of linked list
Node low = first;
Node high = first;
while (high != null && high.next != null && high.next.next != null && high.next != last && head.next.next != last)
{
//visit to next node
low = low.next;
//visit to second next node
high = high.next.next;
}
//This is middle element
return low;
}
}
//Merge two sorted list and return its result
public Node merge_list(Node list1, Node list2)
{
if (list1 == null)
{
//When list1 is empty
return list2;
}
else if (list2 == null)
{
return list1;
}
else
{
//Some auxiliary variables
Node result = null;
Node tail = null;
Node node = null;
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1 != null || list2 != null)
{
if (list1 != null && list2 != null)
{
//When both list contain nodes
if (list1.data < list2.data)
{
//When first list element are smallest
node = list1;
list1 = list1.next;
}
else
{
//When second list element are smallest
node = list2;
list2 = list2.next;
}
}
else if (list1 != null)
{
//When first list contain element
//Get sublist
node = list1;
//Set that list1 empty
list1 = null;
}
else
{
//When second list contain element
//get sublist
node = list2;
list2 = null;
}
if (result == null)
{
//When get first node of resultant list
result = node;
}
else
{
//Add node at end of resultant list
tail.next = node;
}
tail = node;
}
return result;
}
}
//Perform merge sort in given linked list
public Node merge_sort(Node first, Node last)
{
if (first == null || first == last || first.next == null)
{
//When have zero or one node
return first;
}
//Find the relative middle node
Node middle = find_middle(first, last);
//Get the right side sublist
Node right_nodes = merge_sort(middle.next, last);
middle.next = null;
//Get the left side sublist
Node left_nodes = merge_sort(first, middle);
//sorted merge in two list
return merge_list(left_nodes, right_nodes);
}
public static void Main(String[] args)
{
obj.insert(9);
obj.insert(5);
obj.insert(7);
obj.insert(11);
obj.insert(3);
obj.insert(13);
obj.insert(4);
obj.insert(8);
obj.insert(2);
Console.Write("\n Before Sort ");
obj.display();
Console.Write("\n After Sort ");
obj.display();
}
}``````

Output

`````` Before Sort
Linked List : 9 5 7 11 3 13 4 8 2
After Sort
Linked List : 2 3 4 5 7 8 9 11 13``````
``````<?php
// Php Program
// Sort a linked list using merge sort

class Node
{
public \$data;
public \$next;

function __construct(\$data)
{
//set node value
\$this->data = \$data;
\$this->next = null;
}
}
{
public \$tail;
//Class constructors
function __construct()
{
\$this->tail = null;
}
//insert node at last of linke list
public	function insert(\$value)
{
//Create a node
\$node = new Node(\$value);
{
\$this->tail = \$node;
}
else
{
\$this->tail->next = \$node;
\$this->tail = \$node;
}
}
public	function display()
{
{
while (\$temp != null)
{
echo " ". \$temp->data;
\$temp = \$temp->next;
{
//avoid loop
return;
}
}
}
else
{
}
}
//This are returning middle node of given linked list
public	function find_middle(\$first, \$last)
{
if (\$first->next == null || \$first == \$last)
{
return \$first;
}
else
{
//Auxiliary variables
//Get first node of linked list
\$low = \$first;
\$high = \$first;
while (\$high != null && \$high->next != null && \$high->next->next != null && \$high->next != \$last && \$this->head->next->next != \$last)
{
//visit to next node
\$low = \$low->next;
//visit to second next node
\$high = \$high->next->next;
}
//This is middle element
return \$low;
}
}
//Merge two sorted list and return its result
public	function merge_list(\$list1, \$list2)
{
if (\$list1 == null)
{
//When list1 is empty
return \$list2;
}
else if (\$list2 == null)
{
return \$list1;
}
else
{
//Some auxiliary variables
\$result = null;
\$tail = null;
\$node = null;
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (\$list1 != null || \$list2 != null)
{
if (\$list1 != null && \$list2 != null)
{
//When both list contain nodes
if (\$list1->data < \$list2->data)
{
//When first list element are smallest
\$node = \$list1;
\$list1 = \$list1->next;
}
else
{
//When second list element are smallest
\$node = \$list2;
\$list2 = \$list2->next;
}
}
else if (\$list1 != null)
{
//When first list contain element
//Get sublist
\$node = \$list1;
//Set that list1 empty
\$list1 = null;
}
else
{
//When second list contain element
//get sublist
\$node = \$list2;
\$list2 = null;
}
if (\$result == null)
{
//When get first node of resultant list
\$result = \$node;
}
else
{
//Add node at end of resultant list
\$tail->next = \$node;
}
\$tail = \$node;
}
return \$result;
}
}
//Perform merge sort in given linked list
public	function merge_sort(\$first, \$last)
{
if (\$first == null || \$first == \$last || \$first->next == null)
{
//When have zero or one node
return \$first;
}
//Find the relative middle node
\$middle = \$this->find_middle(\$first, \$last);
//Get the right side sublist
\$right_nodes = \$this->merge_sort(\$middle->next, \$last);
\$middle->next = null;
//Get the left side sublist
\$left_nodes = \$this->merge_sort(\$first, \$middle);
//sorted merge in two list
return \$this->merge_list(\$left_nodes, \$right_nodes);
}
}

function main()
{
\$obj->insert(9);
\$obj->insert(5);
\$obj->insert(7);
\$obj->insert(11);
\$obj->insert(3);
\$obj->insert(13);
\$obj->insert(4);
\$obj->insert(8);
\$obj->insert(2);
echo "\n Before Sort ";
\$obj->display();
echo "\n After Sort ";
\$obj->display();
}
main();``````

Output

`````` Before Sort
Linked List : 9 5 7 11 3 13 4 8 2
After Sort
Linked List : 2 3 4 5 7 8 9 11 13``````
``````// Node Js Program
// Sort a linked list using merge sort

class Node
{
constructor(data)
{
//set node value
this.data = data;
this.next = null;
}
}
{
//Class constructors
constructor()
{
this.tail = null;
}
//insert node at last of linke list
insert(value)
{
//Create a node
var node = new Node(value);
{
this.tail = node;
}
else
{
this.tail.next = node;
this.tail = node;
}
}
display()
{
{
while (temp != null)
{
process.stdout.write(" " + temp.data);
temp = temp.next;
{
//avoid loop
return;
}
}
}
else
{
}
}
//This are returning middle node of given linked list
find_middle(first, last)
{
if (first.next == null || first == last)
{
return first;
}
else
{
//Auxiliary variables
//Get first node of linked list
var low = first;
var high = first;
while (high != null && high.next != null && high.next.next != null && high.next != last && this.head.next.next != last)
{
//visit to next node
low = low.next;
//visit to second next node
high = high.next.next;
}
//This is middle element
return low;
}
}
//Merge two sorted list and return its result
merge_list(list1, list2)
{
if (list1 == null)
{
//When list1 is empty
return list2;
}
else if (list2 == null)
{
return list1;
}
else
{
//Some auxiliary variables
var result = null;
var tail = null;
var node = null;
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1 != null || list2 != null)
{
if (list1 != null && list2 != null)
{
//When both list contain nodes
if (list1.data < list2.data)
{
//When first list element are smallest
node = list1;
list1 = list1.next;
}
else
{
//When second list element are smallest
node = list2;
list2 = list2.next;
}
}
else if (list1 != null)
{
//When first list contain element
//Get sublist
node = list1;
//Set that list1 empty
list1 = null;
}
else
{
//When second list contain element
//get sublist
node = list2;
list2 = null;
}
if (result == null)
{
//When get first node of resultant list
result = node;
}
else
{
//Add node at end of resultant list
tail.next = node;
}
tail = node;
}
return result;
}
}
//Perform merge sort in given linked list
merge_sort(first, last)
{
if (first == null || first == last || first.next == null)
{
//When have zero or one node
return first;
}
//Find the relative middle node
var middle = this.find_middle(first, last);
//Get the right side sublist
var right_nodes = this.merge_sort(middle.next, last);
middle.next = null;
//Get the left side sublist
var left_nodes = this.merge_sort(first, middle);
//sorted merge in two list
return this.merge_list(left_nodes, right_nodes);
}
}

function main()
{
obj.insert(9);
obj.insert(5);
obj.insert(7);
obj.insert(11);
obj.insert(3);
obj.insert(13);
obj.insert(4);
obj.insert(8);
obj.insert(2);
process.stdout.write("\n Before Sort ");
obj.display();
process.stdout.write("\n After Sort ");
obj.display();
}
main();``````

Output

`````` Before Sort
Linked List : 9 5 7 11 3 13 4 8 2
After Sort
Linked List : 2 3 4 5 7 8 9 11 13``````
``````#  Python 3 Program
#  Sort a linked list using merge sort

class Node :

def __init__(self, data) :
# set node value
self.data = data
self.next = None

# Class constructors
def __init__(self) :
self.tail = None

# insert node at last of linke list
def insert(self, value) :
# Create a node
node = Node(value)
self.tail = node
else :
self.tail.next = node
self.tail = node

def display(self) :
print("\n Linked List :", end = "")
while (temp != None) :
print(" ", temp.data, end = "")
temp = temp.next
# avoid loop
return

else :
print("Empty Linked List", end = "")

# This are returning middle node of given linked list
def find_middle(self, first, last) :
if (first.next == None or first == last) :
return first
else :
# Auxiliary variables
# Get first node of linked list
low = first
high = first
while (high != None and high.next != None and high.next.next != None and high.next != last and self.head.next.next != last) :
# visit to next node
low = low.next
# visit to second next node
high = high.next.next

# This is middle element
return low

# Merge two sorted list and return its result
def merge_list(self, list1, list2) :
if (list1 == None) :
# When list1 is empty
return list2

elif(list2 == None) :
return list1
else :
# Some auxiliary variables
result = None
tail = None
node = None
#  Combine list elements in sorted order
#  This process takes(m+n) time
#  Here m is size of list1
#  And n is size of list2
while (list1 != None or list2 != None) :
if (list1 != None and list2 != None) :
# When both list contain nodes
if (list1.data < list2.data) :
# When first list element are smallest
node = list1
list1 = list1.next
else :
# When second list element are smallest
node = list2
list2 = list2.next

elif(list1 != None) :
# When first list contain element
# Get sublist
node = list1
# Set that list1 empty
list1 = None
else :
# When second list contain element
# get sublist
node = list2
list2 = None

if (result == None) :
# When get first node of resultant list
result = node
else :
# Add node at end of resultant list
tail.next = node

tail = node

return result

# Perform merge sort in given linked list
def merge_sort(self, first, last) :
if (first == None or first == last or first.next == None) :
# When have zero or one node
return first

# Find the relative middle node
middle = self.find_middle(first, last)
# Get the right side sublist
right_nodes = self.merge_sort(middle.next, last)
middle.next = None
# Get the left side sublist
left_nodes = self.merge_sort(first, middle)
# sorted merge in two list
return self.merge_list(left_nodes, right_nodes)

def main() :
obj.insert(9)
obj.insert(5)
obj.insert(7)
obj.insert(11)
obj.insert(3)
obj.insert(13)
obj.insert(4)
obj.insert(8)
obj.insert(2)
print("\n Before Sort ", end = "")
obj.display()
print("\n After Sort ", end = "")
obj.display()

if __name__ == "__main__": main()``````

Output

`````` Before Sort
Linked List :  9  5  7  11  3  13  4  8  2
After Sort
Linked List :  2  3  4  5  7  8  9  11  13``````
``````#  Ruby Program
#  Sort a linked list using merge sort

class Node

# Define the accessor and reader of class Node
attr_accessor :data, :next

def initialize(data)

# set node value
self.data = data
self.next = nil
end
end

# Class constructors
def initialize()

self.tail = nil
end
# insert node at last of linke list
def insert(value)

# Create a node
node = Node.new(value)

self.tail = node
else

self.tail.next = node
self.tail = node
end
end
def display()

while (temp != nil)

print(" ", temp.data)
temp = temp.next

# avoid loop
return
end
end
else

end
end
# This are returning middle node of given linked list
def find_middle(first, last)

if (first.next == nil || first == last)

return first
else

# Auxiliary variables
# Get first node of linked list
low = first
high = first
while (high != nil && high.next != nil && high.next.next != nil && high.next != last && @head.next.next != last)

# visit to next node
low = low.next
# visit to second next node
high = high.next.next
end
# This is middle element
return low
end
end
# Merge two sorted list and return its result
def merge_list(list1, list2)

if (list1 == nil)

# When list1 is empty
return list2
elsif(list2 == nil)

return list1
else

# Some auxiliary variables
result = nil
tail = nil
node = nil
#  Combine list elements in sorted order
#  This process takes(m+n) time
#  Here m is size of list1
#  And n is size of list2
while (list1 != nil || list2 != nil)

if (list1 != nil && list2 != nil)

# When both list contain nodes
if (list1.data < list2.data)

# When first list element are smallest
node = list1
list1 = list1.next
else

# When second list element are smallest
node = list2
list2 = list2.next
end
elsif(list1 != nil)

# When first list contain element
# Get sublist
node = list1
# Set that list1 empty
list1 = nil
else

# When second list contain element
# get sublist
node = list2
list2 = nil
end
if (result == nil)

# When get first node of resultant list
result = node
else

# Add node at end of resultant list
tail.next = node
end
tail = node
end
return result
end
end
# Perform merge sort in given linked list
def merge_sort(first, last)

if (first == nil || first == last || first.next == nil)

# When have zero or one node
return first
end
# Find the relative middle node
middle = self.find_middle(first, last)
# Get the right side sublist
right_nodes = self.merge_sort(middle.next, last)
middle.next = nil
# Get the left side sublist
left_nodes = self.merge_sort(first, middle)
# sorted merge in two list
return self.merge_list(left_nodes, right_nodes)
end
end
def main()

obj.insert(9)
obj.insert(5)
obj.insert(7)
obj.insert(11)
obj.insert(3)
obj.insert(13)
obj.insert(4)
obj.insert(8)
obj.insert(2)
print("\n Before Sort ")
obj.display()
print("\n After Sort ")
obj.display()
end
main()``````

Output

`````` Before Sort
Linked List : 9 5 7 11 3 13 4 8 2
After Sort
Linked List : 2 3 4 5 7 8 9 11 13``````
``````// Scala Program
// Sort a linked list using merge sort

class Node(var data: Int,
var next: Node)
{
def this(data: Int)
{
this(data, null);
}
}
var tail: Node)
{
//Class constructors
def this()
{
this(null, null);
}
//insert node at last of linke list
def insert(value: Int): Unit = {
//Create a node
var node: Node = new Node(value);
{
this.tail = node;
}
else
{
this.tail.next = node;
this.tail = node;
}
}
def display(): Unit = {
{
while (temp != null)
{
print(" " + temp.data);
temp = temp.next;
{
//avoid loop
return;
}
}
}
else
{
}
}
//This are returning middle node of given linked list
def find_middle(first: Node, last: Node): Node = {

if (first.next == null || first == last)
{
return first;
}
else
{
//Auxiliary variables
//Get first node of linked list
var low: Node = first;
var high: Node = first;
while (high != null && high.next != null && high.next.next != null && high.next != last && head.next.next != last)
{
//visit to next node
low = low.next;
//visit to second next node
high = high.next.next;
}
//This is middle element
return low;
}
}
//Merge two sorted list and return its result
def merge_list(l1: Node, l2: Node): Node =
{
var list1: Node = l1;
var list2: Node = l2;
if (list1 == null)
{
//When list1 is empty
return list2;
}
else if (list2 == null)
{
return list1;
}
else
{
//Some auxiliary variables
var result: Node = null;
var tail: Node = null;
var node: Node = null;
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1 != null || list2 != null)
{
if (list1 != null && list2 != null)
{
//When both list contain nodes
if (list1.data < list2.data)
{
//When first list element are smallest
node = list1;
list1 = list1.next;
}
else
{
//When second list element are smallest
node = list2;
list2 = list2.next;
}
}
else if (list1 != null)
{
//When first list contain element
//Get sublist
node = list1;
//Set that list1 empty
list1 = null;
}
else
{
//When second list contain element
//get sublist
node = list2;
list2 = null;
}
if (result == null)
{
//When get first node of resultant list
result = node;
}
else
{
//Add node at end of resultant list
tail.next = node;
}
tail = node;
}
return result;
}
}
//Perform merge sort in given linked list
def merge_sort(first: Node, last: Node): Node = {
if (first == null || first == last || first.next == null)
{
//When have zero or one node
return first;
}
//Find the relative middle node
var middle: Node = find_middle(first, last);
//Get the right side sublist
var right_nodes: Node = merge_sort(middle.next, last);
middle.next = null;
//Get the left side sublist
var left_nodes: Node = merge_sort(first, middle);
//sorted merge in two list
return merge_list(left_nodes, right_nodes);
}
}
object Main
{
def main(args: Array[String]): Unit = {
obj.insert(9);
obj.insert(5);
obj.insert(7);
obj.insert(11);
obj.insert(3);
obj.insert(13);
obj.insert(4);
obj.insert(8);
obj.insert(2);
print("\n Before Sort ");
obj.display();
print("\n After Sort ");
obj.display();
}
}``````

Output

`````` Before Sort
Linked List : 9 5 7 11 3 13 4 8 2
After Sort
Linked List : 2 3 4 5 7 8 9 11 13``````
``````// Swift Program
// Sort a linked list using merge sort

class Node
{
var data: Int;
var next: Node? ;
init(_ data: Int)
{
//set node value
self.data = data;
self.next = nil;
}
}
{
var tail: Node? ;
//Class constructors
init()
{
self.tail = nil;
}
//insert node at last of linke list
func insert(_ value: Int)
{
//Create a node
let node: Node? = Node(value);
{
self.tail = node;
}
else
{
self.tail!.next = node;
self.tail = node;
}
}
func display()
{
{
print("\n Linked List :", terminator: "");
while (temp != nil)
{
print(" ", temp!.data, terminator: "");
temp = temp!.next;
}
}
else
{
}
}
//This are returning middle node of given linked list
func find_middle(_ first: Node? , _ last : Node? ) -> Node?
{
if (first!.next == nil || first === last)
{
return first;
}
else
{
//Auxiliary variables
//Get first node of linked list
var low: Node? = first;
var high: Node? = first;
while (high != nil && high!.next != nil && high!.next!.next != nil && !(high!.next === last) && !(self.head!.next!.next === last))
{
//visit to next node
low = low!.next;
//visit to second next node
high = high!.next!.next;
}
//This is middle element
return low;
}
}
//Merge two sorted list and return its result
func merge_list(_ l1:  Node? , _ l2 :  Node? ) -> Node?
{
var list1: Node? = l1;
var list2: Node? = l2;
if (list1 == nil)
{
//When list1 is empty
return list2;
}
else if (list2 == nil)
{
return list1;
}
else
{
//Some auxiliary variables
var result: Node? = nil;
var tail: Node? = nil;
var node: Node? = nil;
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1 != nil || list2 != nil)
{
if (list1 != nil && list2 != nil)
{
//When both list contain nodes
if (list1!.data < list2!.data)
{
//When first list element are smallest
node = list1;
list1 = list1!.next;
}
else
{
//When second list element are smallest
node = list2;
list2 = list2!.next;
}
}
else if (list1 != nil)
{
//When first list contain element
//Get sublist
node = list1;
//Set that list1 empty
list1 = nil;
}
else
{
//When second list contain element
//get sublist
node = list2;
list2 = nil;
}
if (result == nil)
{
//When get first node of resultant list
result = node;
}
else
{
//Add node at end of resultant list
tail!.next = node;
}
tail = node;
}
return result;
}
}
//Perform merge sort in given linked list
func merge_sort(_ first: Node? , _ last : Node? ) -> Node?
{
if (first == nil || first === last || first!.next == nil)
{
//When have zero or one node
return first;
}
//Find the relative middle node
let middle: Node? = self.find_middle(first, last);
//Get the right side sublist
let right_nodes: Node? = self.merge_sort(middle!.next, last);
middle!.next = nil;
//Get the left side sublist
let left_nodes: Node? = self.merge_sort(first, middle);
//sorted merge in two list
return self.merge_list(left_nodes, right_nodes);
}
}
func main()
{
obj.insert(9);
obj.insert(5);
obj.insert(7);
obj.insert(11);
obj.insert(3);
obj.insert(13);
obj.insert(4);
obj.insert(8);
obj.insert(2);
print("\n Before Sort ", terminator: "");
obj.display();
print("\n After Sort ", terminator: "");
obj.display();
}
main();``````

Output

`````` Before Sort
Linked List :  9  5  7  11  3  13  4  8  2
After Sort
Linked List :  2  3  4  5  7  8  9  11  13``````

Time Complexity Analysis

The Merge Sort algorithm has an average and worst-case time complexity of O(n log n) for sorting a linked list. Since it recursively divides the linked list into halves, it requires additional memory for storing the recursive call stack, resulting in a space complexity of O(log n).

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.