Skip to main content

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:

  1. If the list is empty or has only one element, it is already sorted. Return the list.

  2. 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.

  3. Recursively sort each half of the list by calling the merge sort function on each half.

  4. 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.

  5. 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
Example of merge sort in linked list
Last updated on by Kalkicode




Comment

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

New Comment