Implementing Merge-Sort using Singly-Linked-List:

Here is the Java code:


class Node
{
public int data;
public Node next;

public Node(int _data)
{
data = _data;
}
}
public class LinkedList
{
int size=0;
private Node root;

public LinkedList(int[] array)
{
insertArray(array);
}

public void insertArray(int[] arr)
{
Node temp = null,temp2 = null;
for(int i:arr)
{
temp = new Node(i);
if(temp2 == null)
{
root = temp2 = temp;
}
else{
temp2.next =temp;
temp2=temp2.next;
}
}
size = arr.length;
}
public void merge_sort()
{
root = merge_sort_internal(root, size);
}
private Node merge_sort_internal(Node head,int size)
{
if(size == 1)
{
head.next=null;
return head;
}
else
{
Node temp = head;
for(int count = 0;count<size/2;++count)
{
temp = temp.next;
}
head = merge_sort_internal(head,size/2);
temp = merge_sort_internal(temp,size - size/2);
head = merge(head,temp,size,size/2);
return head;
}
}
private Node merge(Node list1,Node list2,int total_size,int half)
{
Node head = new Node(-1);//dummy node, gotta delete
Node temp= head;

while(list1 != null && list2 != null)
{
if(list1.data > list2.data)
{
head.next = list2;
list2 = list2.next;
}
else
{
head.next = list1;
list1 = list1.next;
}
head = head.next;
}
for(;list1 != null;list1=list1.next,head = head.next)
head.next = list1;
for(;list2 != null;list2=list2.next,head = head.next)
head.next = list2;
temp = temp.next;
return temp;
}
@Override
public String toString()
{
Node temp = root;
if(temp == null)
return "NULL";
String s = "";
for(;temp!=null;temp = temp.next)
{
s = s+temp.data+" ";
}
return s+"End";
}
public static void main(String[] arg)
{
int[] array = {4,2,5,6,8,1,3,99,3};

LinkedList ll = new LinkedList(array);
ll.merge_sort();
System.out.println(ll);
}
}