# Java Program to Implement Merge Sort Algorithm on Linked List

This is a java program to implement merge sort algorithm using linked list.

Here is the source code of the Java Program to Implement Merge Sort Algorithm on Linked List. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

//This is a java to sort numbers of Linked List using Merge Sort
import java.util.Random;

class Node
{
public int item;
public Node next;

public Node(int val)
{
item = val;
}

public Node()
{}

public void displayNode()
{
System.out.print("[" + item + "] ");
}
}

{
private Node first;

{
first = null;
}

public boolean isEmpty()
{
return (first == null);
}

public void insert(int val)
{
Node newNode = new Node(val);
newNode.next = first;
first = newNode;
}

public void append(Node result)
{
first = result;
}

public void display()
{
Node current = first;
while (current != null)
{
current.displayNode();
current = current.next;
}
System.out.println("");
}

public Node extractFirst()
{
return first;
}

{
while ((b != null) && (b.next != null))
{
b = (b.next).next;
}
return merge(MergeSort(a), MergeSort(b));
}

public Node merge(Node a, Node b)
{
Node temp = new Node();
while ((a != null) && (b != null))
{
if (a.item <= b.item)
{
c.next = a;
c = a;
a = a.next;
}
else
{
c.next = b;
c = b;
b = b.next;
}
}
c.next = (a == null) ? b : a;
}
}

class Merge_Sort
{
public static void main(String[] args)
{
Random random = new Random();
int N = 20;
for (int i = 0; i < N; i++)
object.insert(Math.abs(random.nextInt(100)));

System.out.println("List items before sorting :");
object.display();
object.append(object.MergeSort(object.extractFirst()));
System.out.println("List items after sorting :");
object.display();
}
}


Output:

$javac Merge_Sort.java$ java Merge_Sort

List items before sorting :
                   
List items after sorting :