# 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

{
int data;
};
struct SingleLL
{
};
// Returns the new linked list
{
// 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->tail = NULL;
}
return sll;
}
void appendNode(struct SingleLL *sll, struct LinkNode *node)
{
{
}
else
{
// Append the node at last position
sll->tail->next = node;
}
sll->tail = node;
}
void addNode(struct SingleLL *sll, int data)
{
// Create dynamic node
if (node == NULL)
{
return;
}
else
{
// Set initial node value
node->data = data;
node->next = NULL;
}
appendNode(sll, node);
}
void display(struct SingleLL *sll)
{
{
return;
}
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
{
// Define auxiliary variable
// 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
{
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
{
if (node == NULL || node->next == NULL)
{
return node;
}
else
{
// Find middle node
// Sort right sublist
middle->next = NULL;
// Sort left sublist
return sortedMerge(left, right);
}
}
// Handles the request to perform merge sort
void sort(struct SingleLL *sll)
{
{
return;
}
// Find last node
while (node != NULL && node->next != NULL)
{
// visit to next node
node = node->next;
}
// Set new tail
sll->tail = node;
}
int main()
{
// 3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
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
*/
{
public int data;
{
this.data = data;
this.next = null;
}
}
public class SingleLL
{
public SingleLL()
{
this.tail = null;
}
{
{
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
public void display()
{
{
return;
}
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
{
// Define auxiliary variable
// 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
{
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
{
if (node == null || node.next == null)
{
return node;
}
else
{
// Find middle node
// Sort right sublist
middle.next = null;
// Sort left sublist
return sortedMerge(left, right);
}
}
// Handles the request to perform merge sort
public void sort()
{
{
return;
}
// 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();
// 3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
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
*/

{
public:
int data;
{
this->data = data;
this->next = NULL;
}
};
class SingleLL
{
public:
SingleLL()
{
this->tail = NULL;
}
{
{
}
else
{
// Append the node at last position
this->tail->next = node;
}
this->tail = node;
}
void display()
{
{
cout << "\n Empty linked list\n";
return;
}
while (temp != NULL)
{
cout << " " << temp->data << " →";
// Visit to next node
temp = temp->next;
}
cout << " NULL\n";
}
// Returns the middle node of given linked list
{
// Return the middle node
// Define auxiliary variable
// 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
{
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
{
if (node == NULL || node->next == NULL)
{
return node;
}
else
{
// Find middle node
// Sort right sublist
middle->next = NULL;
// Sort left sublist
return this->sortedMerge(left, right);
}
}
// Handles the request to perform merge sort
void sort()
{
{
return;
}
// 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();
// 3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
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
*/
{
public int data;
{
this.data = data;
this.next = null;
}
}
public class SingleLL
{
public SingleLL()
{
this.tail = null;
}
{
{
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
public void display()
{
{
return;
}
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
{
// Return the middle node
// Define auxiliary variable
// 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
{
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
{
if (node == null || node.next == null)
{
return node;
}
else
{
// Find middle node
// Sort right sublist
middle.next = null;
// Sort left sublist
return sortedMerge(left, right);
}
}
// Handles the request to perform merge sort
public void sort()
{
{
return;
}
// 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();
// 3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
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
*/
{
public \$data;
public \$next;

function __construct(\$data)
{
\$this->data = \$data;
\$this->next = null;
}
}
class SingleLL
{
public \$tail;

function __construct()
{
\$this->tail = null;
}
{
{
}
else
{
// Append the node at last position
\$this->tail->next = \$node;
}
\$this->tail = \$node;
}
public	function display()
{
{
return;
}
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);
\$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()
{
{
return;
}
// 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();
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
*/
{
constructor(data)
{
this.data = data;
this.next = null;
}
}
class SingleLL
{
constructor()
{
this.tail = null;
}
{
{
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
display()
{
{
return;
}
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);
middle.next = null;
// Sort left sublist
var left = this.mergeSort(node);
return this.sortedMerge(left, right);
}
}
// Handles the request to perform merge sort
sort()
{
{
return;
}
// 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();
// 3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
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

def __init__(self, data) :
self.data = data
self.next = None

class SingleLL :

def __init__(self) :
self.tail = None

else :
#  Append the node at last position
self.tail.next = node

self.tail = node

def display(self) :
return

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)
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) :
return

#  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()
#  3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
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

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

def initialize()
self.tail = nil
end

else
#  Append the node at last position
self.tail.next = node
end
self.tail = node
end

def display()
return
end
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)
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()
return
end

#  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()
#  3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
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
*/
{
def this(data: Int)
{
this(data, null);
}
}
{
def this()
{
this(null, null);
}
def addNode(data: Int): Unit = {
{
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
def display(): Unit = {
{
return;
}
while (temp != null)
{
print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
print(" NULL\n");
}
// Returns the middle node of given linked list
// Return the middle node
// Define auxiliary variable
// 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
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
if (node == null || node.next == null)
{
return node;
}
else
{
// Find middle node
// Sort right sublist
middle.next = null;
// Sort left sublist
return this.sortedMerge(left, right);
}
}
// Handles the request to perform merge sort
def sort(): Unit = {
{
return;
}
// 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();
// 3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
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
*/
{
var data: Int;
init(_ data: Int)
{
self.data = data;
self.next = nil;
}
}
class SingleLL
{
init()
{
self.tail = nil;
}
{
{
}
else
{
// Append the node at last position
self.tail!.next = node;
}
self.tail = node;
}
func display()
{
{
return;
}
while (temp  != nil)
{
print("", temp!.data ,"→", terminator: "");
// Visit to next node
temp = temp!.next;
}
print(" NULL");
}
// Returns the middle node of given linked list
{
// Return the middle node
// Define auxiliary variable
// 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
{
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
{
if (node == nil || node!.next == nil)
{
return node;
}
else
{
// Find middle node
// Sort right sublist
middle!.next = nil;
// Sort left sublist
return self.sortedMerge(left, right);
}
}
// Handles the request to perform merge sort
func sort()
{
{
return;
}
// 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();
// 3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
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
*/
{
var data: Int;
constructor(data: Int)
{
this.data = data;
this.next = null;
}
}
class SingleLL
{
constructor()
{
this.tail = null;
}
{
{
}
else
{
// Append the node at last position
this.tail?.next = node;
}
this.tail = node;
}
fun display(): Unit
{
{
return;
}
while (temp != null)
{
print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
print(" NULL\n");
}
// Returns the middle node of given linked list
{
// 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
{
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
{
if (node == null || node.next == null)
{
return node;
}
else
{
// Find middle node
// Sort right sublist
middle?.next = null;
// Sort left sublist
return this.sortedMerge(left, right);
}
}
// Handles the request to perform merge sort
fun sort(): Unit
{
{
return;
}
// 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();
// 3 → 11 → 8 → 5 → -2 → 16 → 9 → NULL
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``````

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