Merge sort for singly linked list

Here given code implementation process.

// 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
Example of merge sort in linked list


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







© 2021, kalkicode.com, All rights reserved