Merge sort for singly linked list
Merge sort is a popular sorting algorithm that works by dividing an array or a linked list into two halves, sorting them independently, and then merging the sorted halves back together. The same approach can be used to sort a singly linked list.
In the case of a singly linked list, the merge sort algorithm can be implemented using a recursive approach. The basic idea is to divide the list into two halves, sort each half recursively, and then merge the two sorted halves back together to create a sorted list.
Here are the basic steps of the merge sort algorithm for a singly linked list:
If the list is empty or has only one element, it is already sorted. Return the list.
Otherwise, divide the list into two halves using the slow-fast pointer technique. Traverse the list using two pointers, one that moves one step at a time (the slow pointer) and one that moves two steps at a time (the fast pointer). When the fast pointer reaches the end of the list, the slow pointer will be pointing to the middle of the list.
Recursively sort each half of the list by calling the merge sort function on each half.
Merge the two sorted halves back together by creating a new list and appending the smaller of the two values at the front of the new list. Continue this process until both halves have been merged into the new list.
Return the sorted list.
By using this approach, the merge sort algorithm can efficiently sort a singly linked list in O(n log n) time complexity, where n is the length of the list.
Program Solution
// C Program
// Merge sort for singly linked list
#include <stdio.h>
#include <stdlib.h> //for malloc function
// Linked List LinkNode
struct LinkNode
{
int data;
struct LinkNode *next;
};
// Singly linked list
struct SingleLL
{
struct LinkNode *head;
struct LinkNode *tail;
};
// Returns the new linked list
struct SingleLL *newLinkedList()
{
// Create memory of head and tail Nodes
struct SingleLL *sll = (struct SingleLL *) malloc(sizeof(struct SingleLL));
if (sll == NULL)
{
printf("Memory overflow\n");
}
else
{
sll->head = NULL;
sll->tail = NULL;
}
return sll;
}
// Add new Node at end of linked list
void appendNode(struct SingleLL *sll, struct LinkNode *node)
{
if (sll->head == NULL)
{
sll->head = node;
}
else
{
// Append the node at last position
sll->tail->next = node;
}
sll->tail = node;
}
// Handles the request of adding new node in linked list
void addNode(struct SingleLL *sll, int data)
{
// Create dynamic node
struct LinkNode *node = (struct LinkNode *) malloc(sizeof(struct LinkNode));
if (node == NULL)
{
printf("Memory overflow to Create LinkNode\n");
return;
}
else
{
// Set initial node value
node->data = data;
node->next = NULL;
}
appendNode(sll, node);
}
// Display linked list element
void display(struct SingleLL *sll)
{
if (sll->head == NULL)
{
printf("\n Empty linked list\n");
return;
}
struct LinkNode *temp = sll->head;
// iterating linked list elements
while (temp != NULL)
{
printf(" %d →", temp->data);
// Visit to next node
temp = temp->next;
}
printf(" NULL\n");
}
// Returns the middle node of given linked list
struct LinkNode *findMiddle(struct LinkNode *node)
{
// Define auxiliary variable
struct LinkNode *middle = node;
struct LinkNode *fast = node;
// Execute the loop until here fast variable is not null
// and its two next node are exist
while (fast != NULL && fast->next != NULL && fast->next->next != NULL)
{
// visit to second next node
fast = fast->next->next;
// visit to next node
middle = middle->next;
}
// Return the middle node
return middle;
}
// sorted merging of node in given sorted sublist
struct LinkNode *sortedMerge(struct LinkNode *x, struct LinkNode *y)
{
if (x == NULL)
{
return y;
}
else if (y == NULL)
{
return x;
}
else
{
if (x->data <= y->data)
{
x->next = sortedMerge(x->next, y);
return x;
}
else
{
y->next = sortedMerge(x, y->next);
return y;
}
}
}
// Splitting the linked list node,
// And combine node using sorted merge function
struct LinkNode *mergeSort(struct LinkNode *node)
{
if (node == NULL || node->next == NULL)
{
return node;
}
else
{
// Find middle node
struct LinkNode *middle = findMiddle(node);
// Sort right sublist
struct LinkNode *right = mergeSort(middle->next);
// split the linked list
middle->next = NULL;
// Sort left sublist
struct LinkNode *left = mergeSort(node);
return sortedMerge(left, right);
}
}
// Handles the request to perform merge sort
void sort(struct SingleLL *sll)
{
if (sll->head == NULL)
{
return;
}
// Set new head
sll->head = mergeSort(sll->head);
struct LinkNode *node = sll->head;
// Find last node
while (node != NULL && node->next != NULL)
{
// visit to next node
node = node->next;
}
// Set new tail
sll->tail = node;
}
int main()
{
// Create a linked list
struct SingleLL *sll = newLinkedList();
// Given of linked list
// 3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
// Construct linked list
addNode(sll, 3);
addNode(sll, 11);
addNode(sll, 8);
addNode(sll, 5);
addNode(sll, -2);
addNode(sll, 16);
addNode(sll, 9);
printf("\n Before sort \n");
display(sll);
// perform sort
sort(sll);
printf("\n After sort \n");
display(sll);
return 0;
}
Output
Before sort
3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
After sort
-2 → 3 → 5 → 8 → 9 → 11 → 16 → NULL
/*
Java Program
Merge sort for singly linked list
*/
// Linked list node
class LinkNode
{
public int data;
public LinkNode next;
public LinkNode(int data)
{
this.data = data;
this.next = null;
}
}
public class SingleLL
{
public LinkNode head;
public LinkNode tail;
public SingleLL()
{
this.head = null;
this.tail = null;
}
// Add new Node at end of linked list
public void addNode(int data)
{
LinkNode node = new LinkNode(data);
if (this.head == null)
{
this.head = node;
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
// Display linked list element
public void display()
{
if (this.head == null)
{
System.out.print("\n Empty linked list\n");
return;
}
LinkNode temp = this.head;
//iterating linked list elements
while (temp != null)
{
System.out.print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
System.out.print(" NULL\n");
}
// Returns the middle node of given linked list
public LinkNode findMiddle(LinkNode node)
{
// Define auxiliary variable
LinkNode middle = node;
LinkNode fast = node;
// Execute the loop until here fast variable is not null
// and its two next node are exist
while (fast != null && fast.next != null && fast.next.next != null)
{
// visit to second next node
fast = fast.next.next;
// visit to next node
middle = middle.next;
}
// Return the middle node
return middle;
}
// sorted merging of node in given sorted sublist
public LinkNode sortedMerge(LinkNode x, LinkNode y)
{
if (x == null)
{
return y;
}
else if (y == null)
{
return x;
}
else
{
if (x.data <= y.data)
{
x.next = sortedMerge(x.next, y);
return x;
}
else
{
y.next = sortedMerge(x, y.next);
return y;
}
}
}
// Splitting the linked list node,
// And combine node using sorted merge function
public LinkNode mergeSort(LinkNode node)
{
if (node == null || node.next == null)
{
return node;
}
else
{
// Find middle node
LinkNode middle = findMiddle(node);
// Sort right sublist
LinkNode right = mergeSort(middle.next);
// split the linked list
middle.next = null;
// Sort left sublist
LinkNode left = mergeSort(node);
return sortedMerge(left, right);
}
}
// Handles the request to perform merge sort
public void sort()
{
if (this.head == null)
{
return;
}
// Set new head
this.head = mergeSort(this.head);
LinkNode node = this.head;
// Find last node
while (node != null && node.next != null)
{
// visit to next node
node = node.next;
}
// Set new tail
this.tail = node;
}
public static void main(String[] args)
{
SingleLL sll = new SingleLL();
// Given of linked list
// 3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
// Construct linked list
sll.addNode(3);
sll.addNode(11);
sll.addNode(8);
sll.addNode(5);
sll.addNode(-2);
sll.addNode(16);
sll.addNode(9);
System.out.print("\n Before sort \n");
sll.display();
// perform sort
sll.sort();
System.out.print("\n After sort \n");
sll.display();
}
}
Output
Before sort
3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
After sort
-2 → 3 → 5 → 8 → 9 → 11 → 16 → NULL
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Merge sort for singly linked list
*/
// Linked list node
class LinkNode
{
public:
int data;
LinkNode *next;
LinkNode(int data)
{
this->data = data;
this->next = NULL;
}
};
class SingleLL
{
public:
LinkNode *head;
LinkNode *tail;
SingleLL()
{
this->head = NULL;
this->tail = NULL;
}
// Add new Node at end of linked list
void addNode(int data)
{
LinkNode *node = new LinkNode(data);
if (this->head == NULL)
{
this->head = node;
}
else
{
// Append the node at last position
this->tail->next = node;
}
this->tail = node;
}
// Display linked list element
void display()
{
if (this->head == NULL)
{
cout << "\n Empty linked list\n";
return;
}
LinkNode *temp = this->head;
//iterating linked list elements
while (temp != NULL)
{
cout << " " << temp->data << " →";
// Visit to next node
temp = temp->next;
}
cout << " NULL\n";
}
// Returns the middle node of given linked list
LinkNode *findMiddle(LinkNode *node)
{
// Return the middle node
// Define auxiliary variable
LinkNode *middle = node;
LinkNode *fast = node;
// Execute the loop until here fast variable is not null
// and its two next node are exist
while (fast != NULL && fast->next != NULL && fast->next->next != NULL)
{
// visit to second next node
fast = fast->next->next;
// visit to next node
middle = middle->next;
}
return middle;
}
// sorted merging of node in given sorted sublist
LinkNode *sortedMerge(LinkNode *x, LinkNode *y)
{
if (x == NULL)
{
return y;
}
else if (y == NULL)
{
return x;
}
else
{
if (x->data <= y->data)
{
x->next = this->sortedMerge(x->next, y);
return x;
}
else
{
y->next = this->sortedMerge(x, y->next);
return y;
}
}
}
// Splitting the linked list node , // And combine node using sorted merge function
LinkNode *mergeSort(LinkNode *node)
{
if (node == NULL || node->next == NULL)
{
return node;
}
else
{
// Find middle node
LinkNode *middle = this->findMiddle(node);
// Sort right sublist
LinkNode *right = this->mergeSort(middle->next);
// split the linked list
middle->next = NULL;
// Sort left sublist
LinkNode *left = this->mergeSort(node);
return this->sortedMerge(left, right);
}
}
// Handles the request to perform merge sort
void sort()
{
if (this->head == NULL)
{
return;
}
// Set new head
this->head = this->mergeSort(this->head);
LinkNode *node = this->head;
// Find last node
while (node != NULL && node->next != NULL)
{
// visit to next node
node = node->next;
}
// Set new tail
this->tail = node;
}
};
int main()
{
SingleLL sll = SingleLL();
// Given of linked list
// 3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
// Construct linked list
sll.addNode(3);
sll.addNode(11);
sll.addNode(8);
sll.addNode(5);
sll.addNode(-2);
sll.addNode(16);
sll.addNode(9);
cout << "\n Before sort \n";
sll.display();
// perform sort
sll.sort();
cout << "\n After sort \n";
sll.display();
return 0;
}
Output
Before sort
3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
After sort
-2 → 3 → 5 → 8 → 9 → 11 → 16 → NULL
// Include namespace system
using System;
/*
C# Program
Merge sort for singly linked list
*/
// Linked list node
public class LinkNode
{
public int data;
public LinkNode next;
public LinkNode(int data)
{
this.data = data;
this.next = null;
}
}
public class SingleLL
{
public LinkNode head;
public LinkNode tail;
public SingleLL()
{
this.head = null;
this.tail = null;
}
// Add new Node at end of linked list
public void addNode(int data)
{
LinkNode node = new LinkNode(data);
if (this.head == null)
{
this.head = node;
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
// Display linked list element
public void display()
{
if (this.head == null)
{
Console.Write("\n Empty linked list\n");
return;
}
LinkNode temp = this.head;
//iterating linked list elements
while (temp != null)
{
Console.Write(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
Console.Write(" NULL\n");
}
// Returns the middle node of given linked list
public LinkNode findMiddle(LinkNode node)
{
// Return the middle node
// Define auxiliary variable
LinkNode middle = node;
LinkNode fast = node;
// Execute the loop until here fast variable is not null
// and its two next node are exist
while (fast != null && fast.next != null && fast.next.next != null)
{
// visit to second next node
fast = fast.next.next;
// visit to next node
middle = middle.next;
}
return middle;
}
// sorted merging of node in given sorted sublist
public LinkNode sortedMerge(LinkNode x, LinkNode y)
{
if (x == null)
{
return y;
}
else if (y == null)
{
return x;
}
else
{
if (x.data <= y.data)
{
x.next = sortedMerge(x.next, y);
return x;
}
else
{
y.next = sortedMerge(x, y.next);
return y;
}
}
}
// Splitting the linked list node
// And combine node using sorted merge function
public LinkNode mergeSort(LinkNode node)
{
if (node == null || node.next == null)
{
return node;
}
else
{
// Find middle node
LinkNode middle = findMiddle(node);
// Sort right sublist
LinkNode right = mergeSort(middle.next);
// split the linked list
middle.next = null;
// Sort left sublist
LinkNode left = mergeSort(node);
return sortedMerge(left, right);
}
}
// Handles the request to perform merge sort
public void sort()
{
if (this.head == null)
{
return;
}
// Set new head
this.head = mergeSort(this.head);
LinkNode node = this.head;
// Find last node
while (node != null && node.next != null)
{
// visit to next node
node = node.next;
}
// Set new tail
this.tail = node;
}
public static void Main(String[] args)
{
SingleLL sll = new SingleLL();
// Given of linked list
// 3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
// Construct linked list
sll.addNode(3);
sll.addNode(11);
sll.addNode(8);
sll.addNode(5);
sll.addNode(-2);
sll.addNode(16);
sll.addNode(9);
Console.Write("\n Before sort \n");
sll.display();
// perform sort
sll.sort();
Console.Write("\n After sort \n");
sll.display();
}
}
Output
Before sort
3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
After sort
-2 → 3 → 5 → 8 → 9 → 11 → 16 → NULL
<?php
/*
Php Program
Merge sort for singly linked list
*/
// Linked list node
class LinkNode
{
public $data;
public $next;
function __construct($data)
{
$this->data = $data;
$this->next = null;
}
}
class SingleLL
{
public $head;
public $tail;
function __construct()
{
$this->head = null;
$this->tail = null;
}
// Add new Node at end of linked list
public function addNode($data)
{
$node = new LinkNode($data);
if ($this->head == null)
{
$this->head = $node;
}
else
{
// Append the node at last position
$this->tail->next = $node;
}
$this->tail = $node;
}
// Display linked list element
public function display()
{
if ($this->head == null)
{
echo "\n Empty linked list\n";
return;
}
$temp = $this->head;
//iterating linked list elements
while ($temp != null)
{
echo " ". $temp->data ." →";
// Visit to next node
$temp = $temp->next;
}
echo " NULL\n";
}
// Returns the middle node of given linked list
public function findMiddle($node)
{
// Return the middle node
// Define auxiliary variable
$middle = $node;
$fast = $node;
// Execute the loop until here fast variable is not null
// and its two next node are exist
while ($fast != null
&& $fast->next != null
&& $fast->next->next != null)
{
// visit to second next node
$fast = $fast->next->next;
// visit to next node
$middle = $middle->next;
}
return $middle;
}
// sorted merging of node in given sorted sublist
public function sortedMerge($x, $y)
{
if ($x == null)
{
return $y;
}
else if ($y == null)
{
return $x;
}
else
{
if ($x->data <= $y->data)
{
$x->next = $this->sortedMerge($x->next, $y);
return $x;
}
else
{
$y->next = $this->sortedMerge($x, $y->next);
return $y;
}
}
}
// Splitting the linked list node
// And combine node using sorted merge function
public function mergeSort($node)
{
if ($node == null || $node->next == null)
{
return $node;
}
else
{
// Find middle node
$middle = $this->findMiddle($node);
// Sort right sublist
$right = $this->mergeSort($middle->next);
// split the linked list
$middle->next = null;
// Sort left sublist
$left = $this->mergeSort($node);
return $this->sortedMerge($left, $right);
}
}
// Handles the request to perform merge sort
public function sort()
{
if ($this->head == null)
{
return;
}
// Set new head
$this->head = $this->mergeSort($this->head);
$node = $this->head;
// Find last node
while ($node != null && $node->next != null)
{
// visit to next node
$node = $node->next;
}
// Set new tail
$this->tail = $node;
}
}
function main()
{
$sll = new SingleLL();
$sll->addNode(3);
$sll->addNode(11);
$sll->addNode(8);
$sll->addNode(5);
$sll->addNode(-2);
$sll->addNode(16);
$sll->addNode(9);
echo "\n Before sort \n";
$sll->display();
$sll->sort();
echo "\n After sort \n";
$sll->display();
}
main();
Output
Before sort
3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
After sort
-2 → 3 → 5 → 8 → 9 → 11 → 16 → NULL
/*
Node Js Program
Merge sort for singly linked list
*/
// Linked list node
class LinkNode
{
constructor(data)
{
this.data = data;
this.next = null;
}
}
class SingleLL
{
constructor()
{
this.head = null;
this.tail = null;
}
// Add new Node at end of linked list
addNode(data)
{
var node = new LinkNode(data);
if (this.head == null)
{
this.head = node;
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
// Display linked list element
display()
{
if (this.head == null)
{
process.stdout.write("\n Empty linked list\n");
return;
}
var temp = this.head;
//iterating linked list elements
while (temp != null)
{
process.stdout.write(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
process.stdout.write(" NULL\n");
}
// Returns the middle node of given linked list
findMiddle(node)
{
// Return the middle node
// Define auxiliary variable
var middle = node;
var fast = node;
// Execute the loop until here fast variable is not null
// and its two next node are exist
while (fast != null && fast.next != null && fast.next.next != null)
{
// visit to second next node
fast = fast.next.next;
// visit to next node
middle = middle.next;
}
return middle;
}
// sorted merging of node in given sorted sublist
sortedMerge(x, y)
{
if (x == null)
{
return y;
}
else if (y == null)
{
return x;
}
else
{
if (x.data <= y.data)
{
x.next = this.sortedMerge(x.next, y);
return x;
}
else
{
y.next = this.sortedMerge(x, y.next);
return y;
}
}
}
// Splitting the linked list node
// And combine node using sorted merge function
mergeSort(node)
{
if (node == null || node.next == null)
{
return node;
}
else
{
// Find middle node
var middle = this.findMiddle(node);
// Sort right sublist
var right = this.mergeSort(middle.next);
// split the linked list
middle.next = null;
// Sort left sublist
var left = this.mergeSort(node);
return this.sortedMerge(left, right);
}
}
// Handles the request to perform merge sort
sort()
{
if (this.head == null)
{
return;
}
// Set new head
this.head = this.mergeSort(this.head);
var node = this.head;
// Find last node
while (node != null && node.next != null)
{
// visit to next node
node = node.next;
}
// Set new tail
this.tail = node;
}
}
function main()
{
var sll = new SingleLL();
// Given of linked list
// 3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
// Construct linked list
sll.addNode(3);
sll.addNode(11);
sll.addNode(8);
sll.addNode(5);
sll.addNode(-2);
sll.addNode(16);
sll.addNode(9);
process.stdout.write("\n Before sort \n");
sll.display();
// perform sort
sll.sort();
process.stdout.write("\n After sort \n");
sll.display();
}
main();
Output
Before sort
3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
After sort
-2 → 3 → 5 → 8 → 9 → 11 → 16 → NULL
# Python 3 Program
# Merge sort for singly linked list
# Linked list node
class LinkNode :
def __init__(self, data) :
self.data = data
self.next = None
class SingleLL :
def __init__(self) :
self.head = None
self.tail = None
# Add new Node at end of linked list
def addNode(self, data) :
node = LinkNode(data)
if (self.head == None) :
self.head = node
else :
# Append the node at last position
self.tail.next = node
self.tail = node
# Display linked list element
def display(self) :
if (self.head == None) :
print("\n Empty linked list")
return
temp = self.head
# iterating linked list elements
while (temp != None) :
print("", temp.data ,"→", end = "")
# Visit to next node
temp = temp.next
print(" NULL")
# Returns the middle node of given linked list
def findMiddle(self, node) :
# Define auxiliary variable
middle = node
fast = node
# Execute the loop until here fast variable is not null
# and its two next node are exist
while (fast != None and fast.next != None and fast.next.next != None) :
# visit to second next node
fast = fast.next.next
# visit to next node
middle = middle.next
# Return the middle node
return middle
# sorted merging of node in given sorted sublist
def sortedMerge(self, x, y) :
if (x == None) :
return y
elif(y == None) :
return x
else :
if (x.data <= y.data) :
x.next = self.sortedMerge(x.next, y)
return x
else :
y.next = self.sortedMerge(x, y.next)
return y
# Splitting the linked list node
# And combine node using sorted merge function
def mergeSort(self, node) :
if (node == None or node.next == None) :
return node
else :
# Find middle node
middle = self.findMiddle(node)
# Sort right sublist
right = self.mergeSort(middle.next)
# split the linked list
middle.next = None
# Sort left sublist
left = self.mergeSort(node)
return self.sortedMerge(left, right)
# Handles the request to perform merge sort
def sort(self) :
if (self.head == None) :
return
# Set new head
self.head = self.mergeSort(self.head)
node = self.head
# Find last node
while (node != None and node.next != None) :
# visit to next node
node = node.next
# Set new tail
self.tail = node
def main() :
sll = SingleLL()
# Given of linked list
# 3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
# Construct linked list
sll.addNode(3)
sll.addNode(11)
sll.addNode(8)
sll.addNode(5)
sll.addNode(-2)
sll.addNode(16)
sll.addNode(9)
print("\n Before sort ")
sll.display()
# perform sort
sll.sort()
print("\n After sort ")
sll.display()
if __name__ == "__main__": main()
Output
Before sort
3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
After sort
-2 → 3 → 5 → 8 → 9 → 11 → 16 → NULL
# Ruby Program
# Merge sort for singly linked list
# Linked list node
class LinkNode
# Define the accessor and reader of class LinkNode
attr_reader :data, :next
attr_accessor :data, :next
def initialize(data)
self.data = data
self.next = nil
end
end
class SingleLL
# Define the accessor and reader of class SingleLL
attr_reader :head, :tail
attr_accessor :head, :tail
def initialize()
self.head = nil
self.tail = nil
end
# Add new Node at end of linked list
def addNode(data)
node = LinkNode.new(data)
if (self.head == nil)
self.head = node
else
# Append the node at last position
self.tail.next = node
end
self.tail = node
end
# Display linked list element
def display()
if (self.head == nil)
print("\n Empty linked list\n")
return
end
temp = self.head
# iterating linked list elements
while (temp != nil)
print(" ", temp.data ," →")
# Visit to next node
temp = temp.next
end
print(" NULL\n")
end
# Returns the middle node of given linked list
def findMiddle(node)
# Define auxiliary variable
middle = node
fast = node
# Execute the loop until here fast variable is not null
# and its two next node are exist
while (fast != nil && fast.next != nil && fast.next.next != nil)
# visit to second next node
fast = fast.next.next
# visit to next node
middle = middle.next
end
# Return the middle node
return middle
end
# sorted merging of node in given sorted sublist
def sortedMerge(x, y)
if (x == nil)
return y
elsif(y == nil)
return x
else
if (x.data <= y.data)
x.next = self.sortedMerge(x.next, y)
return x
else
y.next = self.sortedMerge(x, y.next)
return y
end
end
end
# Splitting the linked list node
# And combine node using sorted merge function
def mergeSort(node)
if (node == nil || node.next == nil)
return node
else
# Find middle node
middle = self.findMiddle(node)
# Sort right sublist
right = self.mergeSort(middle.next)
# split the linked list
middle.next = nil
# Sort left sublist
left = self.mergeSort(node)
return self.sortedMerge(left, right)
end
end
# Handles the request to perform merge sort
def sort()
if (self.head == nil)
return
end
# Set new head
self.head = self.mergeSort(self.head)
node = self.head
# Find last node
while (node != nil && node.next != nil)
# visit to next node
node = node.next
end
# Set new tail
self.tail = node
end
end
def main()
sll = SingleLL.new()
# Given of linked list
# 3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
# Construct linked list
sll.addNode(3)
sll.addNode(11)
sll.addNode(8)
sll.addNode(5)
sll.addNode(-2)
sll.addNode(16)
sll.addNode(9)
print("\n Before sort \n")
sll.display()
# perform sort
sll.sort()
print("\n After sort \n")
sll.display()
end
main()
Output
Before sort
3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
After sort
-2 → 3 → 5 → 8 → 9 → 11 → 16 → NULL
/*
Scala Program
Merge sort for singly linked list
*/
// Linked list node
class LinkNode(var data: Int , var next: LinkNode)
{
def this(data: Int)
{
this(data, null);
}
}
class SingleLL(var head: LinkNode , var tail: LinkNode)
{
def this()
{
this(null, null);
}
// Add new Node at end of linked list
def addNode(data: Int): Unit = {
var node: LinkNode = new LinkNode(data);
if (this.head == null)
{
this.head = node;
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
// Display linked list element
def display(): Unit = {
if (this.head == null)
{
print("\n Empty linked list\n");
return;
}
var temp: LinkNode = this.head;
//iterating linked list elements
while (temp != null)
{
print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
print(" NULL\n");
}
// Returns the middle node of given linked list
def findMiddle(node: LinkNode): LinkNode = {
// Return the middle node
// Define auxiliary variable
var middle: LinkNode = node;
var fast: LinkNode = node;
// Execute the loop until here fast variable is not null
// and its two next node are exist
while (fast != null
&& fast.next != null
&& fast.next.next != null)
{
// visit to second next node
fast = fast.next.next;
// visit to next node
middle = middle.next;
}
return middle;
}
// sorted merging of node in given sorted sublist
def sortedMerge(x: LinkNode, y: LinkNode): LinkNode = {
if (x == null)
{
return y;
}
else if (y == null)
{
return x;
}
else
{
if (x.data <= y.data)
{
x.next = this.sortedMerge(x.next, y);
return x;
}
else
{
y.next = this.sortedMerge(x, y.next);
return y;
}
}
}
// Splitting the linked list node
// And combine node using sorted merge function
def mergeSort(node: LinkNode): LinkNode = {
if (node == null || node.next == null)
{
return node;
}
else
{
// Find middle node
var middle: LinkNode = this.findMiddle(node);
// Sort right sublist
var right: LinkNode = this.mergeSort(middle.next);
// split the linked list
middle.next = null;
// Sort left sublist
var left: LinkNode = this.mergeSort(node);
return this.sortedMerge(left, right);
}
}
// Handles the request to perform merge sort
def sort(): Unit = {
if (this.head == null)
{
return;
}
// Set new head
this.head = this.mergeSort(this.head);
var node: LinkNode = this.head;
// Find last node
while (node != null && node.next != null)
{
// visit to next node
node = node.next;
}
// Set new tail
this.tail = node;
}
}
object Main
{
def main(args: Array[String]): Unit = {
var sll: SingleLL = new SingleLL();
// Given of linked list
// 3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
// Construct linked list
sll.addNode(3);
sll.addNode(11);
sll.addNode(8);
sll.addNode(5);
sll.addNode(-2);
sll.addNode(16);
sll.addNode(9);
print("\n Before sort \n");
sll.display();
// perform sort
sll.sort();
print("\n After sort \n");
sll.display();
}
}
Output
Before sort
3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
After sort
-2 → 3 → 5 → 8 → 9 → 11 → 16 → NULL
/*
Swift 4 Program
Merge sort for singly linked list
*/
// Linked list node
class LinkNode
{
var data: Int;
var next: LinkNode? ;
init(_ data: Int)
{
self.data = data;
self.next = nil;
}
}
class SingleLL
{
var head: LinkNode? ;
var tail: LinkNode? ;
init()
{
self.head = nil;
self.tail = nil;
}
// Add new Node at end of linked list
func addNode(_ data: Int)
{
let node: LinkNode? = LinkNode(data);
if (self.head == nil)
{
self.head = node;
}
else
{
// Append the node at last position
self.tail!.next = node;
}
self.tail = node;
}
// Display linked list element
func display()
{
if (self.head == nil)
{
print("\n Empty linked list");
return;
}
var temp: LinkNode? = self.head;
//iterating linked list elements
while (temp != nil)
{
print("", temp!.data ,"→", terminator: "");
// Visit to next node
temp = temp!.next;
}
print(" NULL");
}
// Returns the middle node of given linked list
func findMiddle(_ node: LinkNode? )->LinkNode?
{
// Return the middle node
// Define auxiliary variable
var middle: LinkNode? = node;
var fast: LinkNode? = node;
// Execute the loop until here fast variable is not null
// and its two next node are exist
while (fast != nil && fast!.next != nil && fast!.next!.next != nil)
{
// visit to second next node
fast = fast!.next!.next;
// visit to next node
middle = middle!.next;
}
return middle;
}
// sorted merging of node in given sorted sublist
func sortedMerge(_ x: LinkNode? , _ y : LinkNode? )->LinkNode?
{
if (x == nil)
{
return y;
}
else if (y == nil)
{
return x;
}
else
{
if (x!.data <= y!.data)
{
x!.next = self.sortedMerge(x!.next, y);
return x;
}
else
{
y!.next = self.sortedMerge(x, y!.next);
return y;
}
}
}
// Splitting the linked list node
// And combine node using sorted merge function
func mergeSort(_ node: LinkNode? )->LinkNode?
{
if (node == nil || node!.next == nil)
{
return node;
}
else
{
// Find middle node
let middle: LinkNode? = self.findMiddle(node);
// Sort right sublist
let right: LinkNode? = self.mergeSort(middle!.next);
// split the linked list
middle!.next = nil;
// Sort left sublist
let left: LinkNode? = self.mergeSort(node);
return self.sortedMerge(left, right);
}
}
// Handles the request to perform merge sort
func sort()
{
if (self.head == nil)
{
return;
}
// Set new head
self.head = self.mergeSort(self.head);
var node: LinkNode? = self.head;
// Find last node
while (node != nil && node!.next != nil)
{
// visit to next node
node = node!.next;
}
// Set new tail
self.tail = node;
}
}
func main()
{
let sll: SingleLL = SingleLL();
// Given of linked list
// 3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
// Construct linked list
sll.addNode(3);
sll.addNode(11);
sll.addNode(8);
sll.addNode(5);
sll.addNode(-2);
sll.addNode(16);
sll.addNode(9);
print("\n Before sort ");
sll.display();
// perform sort
sll.sort();
print("\n After sort ");
sll.display();
}
main();
Output
Before sort
3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
After sort
-2 → 3 → 5 → 8 → 9 → 11 → 16 → NULL
/*
Kotlin Program
Merge sort for singly linked list
*/
// Linked list node
class LinkNode
{
var data: Int;
var next: LinkNode ? ;
constructor(data: Int)
{
this.data = data;
this.next = null;
}
}
class SingleLL
{
var head: LinkNode ? ;
var tail: LinkNode ? ;
constructor()
{
this.head = null;
this.tail = null;
}
// Add new Node at end of linked list
fun addNode(data: Int): Unit
{
var node: LinkNode = LinkNode(data);
if (this.head == null)
{
this.head = node;
}
else
{
// Append the node at last position
this.tail?.next = node;
}
this.tail = node;
}
// Display linked list element
fun display(): Unit
{
if (this.head == null)
{
print("\n Empty linked list\n");
return;
}
var temp: LinkNode ? = this.head;
//iterating linked list elements
while (temp != null)
{
print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
print(" NULL\n");
}
// Returns the middle node of given linked list
fun findMiddle(node: LinkNode ? ): LinkNode ?
{
// Return the middle node
// Define auxiliary variable
var middle: LinkNode ? = node;
var fast: LinkNode ? = node;
// Execute the loop until here fast variable is not null
// and its two next node are exist
while (fast != null && fast.next != null && fast.next?.next != null)
{
// visit to second next node
fast = fast.next?.next;
// visit to next node
middle = middle?.next;
}
return middle;
}
// sorted merging of node in given sorted sublist
fun sortedMerge(x: LinkNode ? , y : LinkNode ? ): LinkNode ?
{
if (x == null)
{
return y;
}
else if (y == null)
{
return x;
}
else
{
if (x.data <= y.data)
{
x.next = this.sortedMerge(x.next, y);
return x;
}
else
{
y.next = this.sortedMerge(x, y.next);
return y;
}
}
}
// Splitting the linked list node
// And combine node using sorted merge function
fun mergeSort(node: LinkNode ? ): LinkNode ?
{
if (node == null || node.next == null)
{
return node;
}
else
{
// Find middle node
var middle: LinkNode? = this.findMiddle(node);
// Sort right sublist
val right: LinkNode? = this.mergeSort(middle?.next);
// split the linked list
middle?.next = null;
// Sort left sublist
val left: LinkNode? = this.mergeSort(node);
return this.sortedMerge(left, right);
}
}
// Handles the request to perform merge sort
fun sort(): Unit
{
if (this.head == null)
{
return;
}
// Set new head
this.head = this.mergeSort(this.head);
var node: LinkNode ? = this.head;
// Find last node
while (node != null && node.next != null)
{
// visit to next node
node = node.next;
}
// Set new tail
this.tail = node;
}
}
fun main(args: Array < String > ): Unit
{
var sll: SingleLL = SingleLL();
// Given of linked list
// 3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
// Construct linked list
sll.addNode(3);
sll.addNode(11);
sll.addNode(8);
sll.addNode(5);
sll.addNode(-2);
sll.addNode(16);
sll.addNode(9);
print("\n Before sort \n");
sll.display();
// perform sort
sll.sort();
print("\n After sort \n");
sll.display();
}
Output
Before sort
3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
After sort
-2 → 3 → 5 → 8 → 9 → 11 → 16 → NULL

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