# Linked Lists Sort using Merge Sort

Write a program to sort link list using Merge Sort

#### Solution:

``````using System;

{

class Program
{
public static void Main()
{

}
}

{

public Node SortedMerge(Node node1, Node node2)
{
Node result;
if (node1 == null)
return node2;
if (node2 == null)
return node1;

if (node1.Data <= node2.Data)
{
result = node1;
result.Next = SortedMerge(node1.Next, node2);
}
else
{
result = node2;
result.Next = SortedMerge(node1, node2.Next);
}
return result;
}

public Node MergeSort(Node node)
{
if (node?.Next == null)
{
return node;
}

var intermediate = GetIntermediate(node);
var next = intermediate.Next;

intermediate.Next = null;
var left = MergeSort(node);
var right = MergeSort(next);
return SortedMerge(left, right);
}

public Node GetIntermediate(Node node)
{
if (node == null)
return null;

var currentNode = node.Next;
var nextNode = node;

while (currentNode != null)
{
currentNode = currentNode.Next;
if (currentNode == null) continue;
nextNode = nextNode.Next;
currentNode = currentNode.Next;
}
return nextNode;
}

{
var node = new Node(data) {Next = Head};
}

{
{
}
}
}

public class Node
{
public int Data;
public Node Next;

public Node(int data)
{
Data = data;
}
}
}
``````