Skip to main content

Sort a linked list using merge sort

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

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

Idea to Solve the Problem

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

Pseudocode

insert(head, value):
    Create a new node with data = value
    If head is NULL, set head to the new node
    Else, traverse the list and add the new node at the end

display(head):
    Traverse the linked list and print each node's data

find_middle(head, tail):
    If head is NULL or head is the tail, return head
    Initialize low and high pointers to head
    While high is not NULL and high's next and next's next are not NULL and high's next is not tail and head's next's next is not tail:
        Move low to next node
        Move high to next node's next
    Return low

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

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

main():
    Initialize head to NULL
    Insert elements into the linked list
    Print "Before Sort"
    Call display(head)
    Sort the linked list using merge_sort
    Print "After Sort"
    Call display(head)

Algorithm Explanation

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

Code Solution

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

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

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

Output

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

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

Output

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

using namespace std;

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

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

Output

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

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

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

Output

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

//Node of LinkedList
class Node
{
	public $data;
	public $next;

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

function main()
{
	$obj = new MyLinkedList();
	//Create linked list
	$obj->insert(9);
	$obj->insert(5);
	$obj->insert(7);
	$obj->insert(11);
	$obj->insert(3);
	$obj->insert(13);
	$obj->insert(4);
	$obj->insert(8);
	$obj->insert(2);
	echo "\n Before Sort ";
	$obj->display();
	$obj->head = $obj->merge_sort($obj->head, null);
	echo "\n After Sort ";
	$obj->display();
}
main();

Output

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

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

function main()
{
	var obj = new MyLinkedList();
	//Create linked list
	obj.insert(9);
	obj.insert(5);
	obj.insert(7);
	obj.insert(11);
	obj.insert(3);
	obj.insert(13);
	obj.insert(4);
	obj.insert(8);
	obj.insert(2);
	process.stdout.write("\n Before Sort ");
	obj.display();
	obj.head = obj.merge_sort(obj.head, null);
	process.stdout.write("\n After Sort ");
	obj.display();
}
main();

Output

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

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

class MyLinkedList :
	
	# Class constructors
	def __init__(self) :
		self.head = None
		self.tail = None
	
	# insert node at last of linke list
	def insert(self, value) :
		# Create a node
		node = Node(value)
		if (self.head == None) :
			# When linked list empty add first node
			self.head = node
			self.tail = node
		else :
			# Add new node at end of linked list
			self.tail.next = node
			self.tail = node
		
	
	# Display linked list nodes
	def display(self) :
		if (self.head != None) :
			print("\n Linked List :", end = "")
			temp = self.head
			while (temp != None) :
				print(" ", temp.data, end = "")
				temp = temp.next
				if (temp == self.head) :
					# avoid loop
					return
				
			
		else :
			print("Empty Linked List", end = "")
		
	
	# This are returning middle node of given linked list
	def find_middle(self, first, last) :
		if (first.next == None or first == last) :
			return first
		else :
			# Auxiliary variables
			# Get first node of linked list
			low = first
			high = first
			while (high != None and high.next != None and high.next.next != None and high.next != last and self.head.next.next != last) :
				# visit to next node
				low = low.next
				# visit to second next node
				high = high.next.next
			
			# This is middle element
			return low
		
	
	# Merge two sorted list and return its result
	def merge_list(self, list1, list2) :
		if (list1 == None) :
			# When list1 is empty
			return list2
		
		elif(list2 == None) :
			return list1
		else :
			# Some auxiliary variables
			result = None
			tail = None
			node = None
			#  Combine list elements in sorted order
			#  This process takes(m+n) time
			#  Here m is size of list1
			#  And n is size of list2
			while (list1 != None or list2 != None) :
				if (list1 != None and list2 != None) :
					# When both list contain nodes
					if (list1.data < list2.data) :
						# When first list element are smallest
						node = list1
						list1 = list1.next
					else :
						# When second list element are smallest
						node = list2
						list2 = list2.next
					
				
				elif(list1 != None) :
					# When first list contain element
					# Get sublist
					node = list1
					# Set that list1 empty
					list1 = None
				else :
					# When second list contain element
					# get sublist
					node = list2
					list2 = None
				
				if (result == None) :
					# When get first node of resultant list
					result = node
				else :
					# Add node at end of resultant list
					tail.next = node
				
				tail = node
			
			return result
		
	
	# Perform merge sort in given linked list
	def merge_sort(self, first, last) :
		if (first == None or first == last or first.next == None) :
			# When have zero or one node
			return first
		
		# Find the relative middle node
		middle = self.find_middle(first, last)
		# Get the right side sublist
		right_nodes = self.merge_sort(middle.next, last)
		# Separate linked list elements
		middle.next = None
		# Get the left side sublist
		left_nodes = self.merge_sort(first, middle)
		# sorted merge in two list
		return self.merge_list(left_nodes, right_nodes)
	

def main() :
	obj = MyLinkedList()
	# Create linked list
	obj.insert(9)
	obj.insert(5)
	obj.insert(7)
	obj.insert(11)
	obj.insert(3)
	obj.insert(13)
	obj.insert(4)
	obj.insert(8)
	obj.insert(2)
	print("\n Before Sort ", end = "")
	obj.display()
	obj.head = obj.merge_sort(obj.head, None)
	print("\n After Sort ", end = "")
	obj.display()

if __name__ == "__main__": main()

Output

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

# Node of LinkedList
class Node 

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

	def initialize(data)
	
		# set node value
		self.data = data
		self.next = nil
	end
end
class MyLinkedList 

	# Define the accessor and reader of class MyLinkedList  
	attr_reader :head, :tail
	attr_accessor :head, :tail


	
	# Class constructors
	def initialize()
	
		self.head = nil
		self.tail = nil
	end
	# insert node at last of linke list
	def insert(value)
	
		# Create a node
		node = Node.new(value)
		if (self.head == nil)
		
			# When linked list empty add first node
			self.head = node
			self.tail = node
		else
		
			# Add new node at end of linked list
			self.tail.next = node
			self.tail = node
		end
	end
	# Display linked list nodes
	def display()
	
		if (self.head != nil)
		
			print("\n Linked List :")
			temp = self.head
			while (temp != nil)
			
				print(" ", temp.data)
				temp = temp.next
				if (temp == self.head)
				
					# avoid loop
					return
				end
			end
		else
		
			print("Empty Linked List")
		end
	end
	# This are returning middle node of given linked list
	def find_middle(first, last)
	
		if (first.next == nil || first == last)
		
			return first
		else
		
			# Auxiliary variables
			# Get first node of linked list
			low = first
			high = first
			while (high != nil && high.next != nil && high.next.next != nil && high.next != last && @head.next.next != last)
			
				# visit to next node
				low = low.next
				# visit to second next node
				high = high.next.next
			end
			# This is middle element
			return low
		end
	end
	# Merge two sorted list and return its result
	def merge_list(list1, list2)
	
		if (list1 == nil)
		
			# When list1 is empty
			return list2
		elsif(list2 == nil)
		
			return list1
		else
		
			# Some auxiliary variables
			result = nil
			tail = nil
			node = nil
			#  Combine list elements in sorted order
			#  This process takes(m+n) time
			#  Here m is size of list1
			#  And n is size of list2
			while (list1 != nil || list2 != nil)
			
				if (list1 != nil && list2 != nil)
				
					# When both list contain nodes
					if (list1.data < list2.data)
					
						# When first list element are smallest
						node = list1
						list1 = list1.next
					else
					
						# When second list element are smallest
						node = list2
						list2 = list2.next
					end
				elsif(list1 != nil)
				
					# When first list contain element
					# Get sublist
					node = list1
					# Set that list1 empty
					list1 = nil
				else
				
					# When second list contain element
					# get sublist
					node = list2
					list2 = nil
				end
				if (result == nil)
				
					# When get first node of resultant list
					result = node
				else
				
					# Add node at end of resultant list
					tail.next = node
				end
				tail = node
			end
			return result
		end
	end
	# Perform merge sort in given linked list
	def merge_sort(first, last)
	
		if (first == nil || first == last || first.next == nil)
		
			# When have zero or one node
			return first
		end
		# Find the relative middle node
		middle = self.find_middle(first, last)
		# Get the right side sublist
		right_nodes = self.merge_sort(middle.next, last)
		# Separate linked list elements
		middle.next = nil
		# Get the left side sublist
		left_nodes = self.merge_sort(first, middle)
		# sorted merge in two list
		return self.merge_list(left_nodes, right_nodes)
	end
end
def main()

	obj = MyLinkedList.new()
	# Create linked list
	obj.insert(9)
	obj.insert(5)
	obj.insert(7)
	obj.insert(11)
	obj.insert(3)
	obj.insert(13)
	obj.insert(4)
	obj.insert(8)
	obj.insert(2)
	print("\n Before Sort ")
	obj.display()
	obj.head = obj.merge_sort(obj.head, nil)
	print("\n After Sort ")
	obj.display()
end
main()

Output

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

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

Output

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

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

Output

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

Time Complexity Analysis

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





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