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
If head is NULL, set head to the new node
Else, traverse the list and add the new node at the end
display(head):
Traverse the linked list and print each node's data
find_middle(head, tail):
If head is NULL or head is the tail, return head
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():
Initialize head to NULL
Insert elements into the linked list
Print "Before Sort"
Call display(head)
Sort the linked list using merge_sort
Print "After Sort"
Call display(head)
Algorithm Explanation
- The
insert
function adds a new node with a given value at the end of the linked list. - The
display
function traverses the linked list and prints each node's data. - The
find_middle
function returns the middle node between thehead
andtail
nodes. - The
merge_list
function merges two sorted linked lists and returns the merged result. - The
merge_sort
function recursively divides the linked list into sublists, sorts them, and merges the sorted sublists using themerge_list
function. - In the
main
function, initialize thehead
of the linked list, insert elements into the linked list, display the linked list before sorting, apply themerge_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;
};
//Add new node at end of linked list
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;
if ( *head == NULL)
{
*head = node;
}
else
{
struct Node *temp = *head;
//find last node
while (temp->next != NULL)
{
temp = temp->next;
}
//add node at last possition
temp->next = node;
}
}
}
//Display linked list element
void display(struct Node *head)
{
if (head == NULL)
{
printf("Empty linked list");
return;
}
struct Node *temp = head;
printf("\n Linked List :");
while (temp != NULL)
{
printf(" %d", temp->data);
temp = temp->next;
if (temp == head)
{
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)
{
if (head->next == NULL || head == tail)
{
return head;
}
else
{
//Auxiliary variables
struct Node *low = head;
struct Node *high = head;
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);
//Separate linked list elements
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()
{
struct Node *head = NULL;
//Create linked list
insert( &head, 9);
insert( &head, 5);
insert( &head, 7);
insert( &head, 11);
insert( &head, 3);
insert( &head, 13);
insert( &head, 4);
insert( &head, 8);
insert( &head, 2);
printf("\n Before Sort ");
display(head);
head = merge_sort(head, NULL);
printf("\n After Sort ");
display(head);
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
//Node of LinkedList
class Node
{
public int data;
public Node next;
public Node(int data)
{
//set node value
this.data = data;
this.next = null;
}
}
class MyLinkedList
{
public Node head;
public Node tail;
//Class constructors
public MyLinkedList()
{
this.head = null;
this.tail = null;
}
//insert node at last of linke list
public void insert(int value)
{
//Create a node
Node node = new Node(value);
if (this.head == null)
{
//When linked list empty add first node
this.head = node;
this.tail = node;
}
else
{
//Add new node at end of linked list
this.tail.next = node;
this.tail = node;
}
}
//Display linked list nodes
public void display()
{
if (this.head != null)
{
System.out.print("\n Linked List :");
Node temp = this.head;
while (temp != null)
{
System.out.print(" " + temp.data);
temp = temp.next;
if (temp == this.head)
{
//avoid loop
return;
}
}
}
else
{
System.out.println("Empty Linked List");
}
}
//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);
//Separate linked list elements
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)
{
MyLinkedList obj = new MyLinkedList();
//Create linked list
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();
obj.head = obj.merge_sort(obj.head, null);
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
//Node of LinkedList
class Node
{
public: int data;
Node * next;
Node(int data)
{
//set node value
this->data = data;
this->next = NULL;
}
};
class MyLinkedList
{
public: Node * head;
Node * tail;
//Class constructors
MyLinkedList()
{
this->head = NULL;
this->tail = NULL;
}
//insert node at last of linke list
void insert(int value)
{
//Create a node
Node * node = new Node(value);
if (this->head == NULL)
{
//When linked list empty add first node
this->head = node;
this->tail = node;
}
else
{
//Add new node at end of linked list
this->tail->next = node;
this->tail = node;
}
}
//Display linked list nodes
void display()
{
if (this->head != NULL)
{
cout << "\n Linked List :";
Node * temp = this->head;
while (temp != NULL)
{
cout << " " << temp->data;
temp = temp->next;
if (temp == this->head)
{
//avoid loop
return;
}
}
}
else
{
cout << "Empty Linked List";
}
}
//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);
//Separate linked list elements
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()
{
MyLinkedList obj = MyLinkedList();
//Create linked list
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();
obj.head = obj.merge_sort(obj.head, NULL);
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
//Node of LinkedList
class Node
{
public int data;
public Node next;
public Node(int data)
{
//set node value
this.data = data;
this.next = null;
}
}
class MyLinkedList
{
public Node head;
public Node tail;
//Class constructors
public MyLinkedList()
{
this.head = null;
this.tail = null;
}
//insert node at last of linke list
public void insert(int value)
{
//Create a node
Node node = new Node(value);
if (this.head == null)
{
//When linked list empty add first node
this.head = node;
this.tail = node;
}
else
{
//Add new node at end of linked list
this.tail.next = node;
this.tail = node;
}
}
//Display linked list nodes
public void display()
{
if (this.head != null)
{
Console.Write("\n Linked List :");
Node temp = this.head;
while (temp != null)
{
Console.Write(" " + temp.data);
temp = temp.next;
if (temp == this.head)
{
//avoid loop
return;
}
}
}
else
{
Console.WriteLine("Empty Linked List");
}
}
//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);
//Separate linked list elements
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)
{
MyLinkedList obj = new MyLinkedList();
//Create linked list
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();
obj.head = obj.merge_sort(obj.head, null);
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
//Node of LinkedList
class Node
{
public $data;
public $next;
function __construct($data)
{
//set node value
$this->data = $data;
$this->next = null;
}
}
class MyLinkedList
{
public $head;
public $tail;
//Class constructors
function __construct()
{
$this->head = null;
$this->tail = null;
}
//insert node at last of linke list
public function insert($value)
{
//Create a node
$node = new Node($value);
if ($this->head == null)
{
//When linked list empty add first node
$this->head = $node;
$this->tail = $node;
}
else
{
//Add new node at end of linked list
$this->tail->next = $node;
$this->tail = $node;
}
}
//Display linked list nodes
public function display()
{
if ($this->head != null)
{
echo "\n Linked List :";
$temp = $this->head;
while ($temp != null)
{
echo " ". $temp->data;
$temp = $temp->next;
if ($temp == $this->head)
{
//avoid loop
return;
}
}
}
else
{
echo "Empty Linked List";
}
}
//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);
//Separate linked list elements
$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 = new MyLinkedList();
//Create linked list
$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();
$obj->head = $obj->merge_sort($obj->head, null);
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
//Node of LinkedList
class Node
{
constructor(data)
{
//set node value
this.data = data;
this.next = null;
}
}
class MyLinkedList
{
//Class constructors
constructor()
{
this.head = null;
this.tail = null;
}
//insert node at last of linke list
insert(value)
{
//Create a node
var node = new Node(value);
if (this.head == null)
{
//When linked list empty add first node
this.head = node;
this.tail = node;
}
else
{
//Add new node at end of linked list
this.tail.next = node;
this.tail = node;
}
}
//Display linked list nodes
display()
{
if (this.head != null)
{
process.stdout.write("\n Linked List :");
var temp = this.head;
while (temp != null)
{
process.stdout.write(" " + temp.data);
temp = temp.next;
if (temp == this.head)
{
//avoid loop
return;
}
}
}
else
{
process.stdout.write("Empty Linked List");
}
}
//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);
//Separate linked list elements
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()
{
var obj = new MyLinkedList();
//Create linked list
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();
obj.head = obj.merge_sort(obj.head, null);
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
# Node of LinkedList
class Node :
def __init__(self, data) :
# set node value
self.data = data
self.next = None
class MyLinkedList :
# Class constructors
def __init__(self) :
self.head = None
self.tail = None
# insert node at last of linke list
def insert(self, value) :
# Create a node
node = Node(value)
if (self.head == None) :
# When linked list empty add first node
self.head = node
self.tail = node
else :
# Add new node at end of linked list
self.tail.next = node
self.tail = node
# Display linked list nodes
def display(self) :
if (self.head != None) :
print("\n Linked List :", end = "")
temp = self.head
while (temp != None) :
print(" ", temp.data, end = "")
temp = temp.next
if (temp == self.head) :
# 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)
# Separate linked list elements
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 = MyLinkedList()
# Create linked list
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()
obj.head = obj.merge_sort(obj.head, None)
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
# Node of LinkedList
class Node
# Define the accessor and reader of class Node
attr_reader :data, :next
attr_accessor :data, :next
def initialize(data)
# set node value
self.data = data
self.next = nil
end
end
class MyLinkedList
# Define the accessor and reader of class MyLinkedList
attr_reader :head, :tail
attr_accessor :head, :tail
# Class constructors
def initialize()
self.head = nil
self.tail = nil
end
# insert node at last of linke list
def insert(value)
# Create a node
node = Node.new(value)
if (self.head == nil)
# When linked list empty add first node
self.head = node
self.tail = node
else
# Add new node at end of linked list
self.tail.next = node
self.tail = node
end
end
# Display linked list nodes
def display()
if (self.head != nil)
print("\n Linked List :")
temp = self.head
while (temp != nil)
print(" ", temp.data)
temp = temp.next
if (temp == self.head)
# avoid loop
return
end
end
else
print("Empty Linked List")
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)
# Separate linked list elements
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 = MyLinkedList.new()
# Create linked list
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()
obj.head = obj.merge_sort(obj.head, nil)
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
//Node of LinkedList
class Node(var data: Int,
var next: Node)
{
def this(data: Int)
{
this(data, null);
}
}
class MyLinkedList(var head: Node,
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);
if (this.head == null)
{
//When linked list empty add first node
this.head = node;
this.tail = node;
}
else
{
//Add new node at end of linked list
this.tail.next = node;
this.tail = node;
}
}
//Display linked list nodes
def display(): Unit = {
if (this.head != null)
{
print("\n Linked List :");
var temp: Node = this.head;
while (temp != null)
{
print(" " + temp.data);
temp = temp.next;
if (temp == this.head)
{
//avoid loop
return;
}
}
}
else
{
print("Empty Linked List");
}
}
//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);
//Separate linked list elements
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 = {
var obj: MyLinkedList = new MyLinkedList();
//Create linked list
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();
obj.head = obj.merge_sort(obj.head, null);
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
//Node of LinkedList
class Node
{
var data: Int;
var next: Node? ;
init(_ data: Int)
{
//set node value
self.data = data;
self.next = nil;
}
}
class MyLinkedList
{
var head: Node? ;
var tail: Node? ;
//Class constructors
init()
{
self.head = nil;
self.tail = nil;
}
//insert node at last of linke list
func insert(_ value: Int)
{
//Create a node
let node: Node? = Node(value);
if (self.head == nil)
{
//When linked list empty add first node
self.head = node;
self.tail = node;
}
else
{
//Add new node at end of linked list
self.tail!.next = node;
self.tail = node;
}
}
//Display linked list nodes
func display()
{
if (self.head != nil)
{
print("\n Linked List :", terminator: "");
var temp: Node? = self.head;
while (temp != nil)
{
print(" ", temp!.data, terminator: "");
temp = temp!.next;
}
}
else
{
print("Empty Linked List", terminator: "");
}
}
//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);
//Separate linked list elements
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()
{
let obj: MyLinkedList = MyLinkedList();
//Create linked list
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();
obj.head = obj.merge_sort(obj.head, nil);
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).
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.
New Comment