ISourceCode

Make the frequent cases fast and the rare case correct

MergeSort of a Linked List – Java

In this article you can find code for merge sort implementation using linked lists.

Procedure:

MergeSort(head node)

1) If head is NULL or there is only one element in the Linked List then return the node.
2) Else divide the linked list into two halves a and b.
3) Sort recursively the two halves a and b
4) Merge the sorted a and b
5) append the head to the remaining merged list.

You can also check the Formatted code here

class Node
{
	public int item;
	public Node next;
	public Node(int val)
	{
		item = val;
	}
	public Node()
	{}
	public void displayNode()
	{
		System.out.println("[" + item + "] ");
	}
}
class LinkedList
{
	private Node first;
	public LinkedList()
	{
		first = null;
	}
	public boolean isEmpty()
	{
		return (first==null);
	}
	public void insert(int val)//inserts at beginning of list
	{
		Node newNode = new Node(val);
		newNode.next = first;
		first = newNode;
	}
	public void append(Node result)
	{
		first = result;
	}
	public void display()
	{
		System.out.println("List items from first to last :");
		Node current = first;
		while(current != null)
		{
			current.displayNode();
			current = current.next;
		}
		System.out.println("");
	}
	public Node extractFirst()
	{
		return first;
	}
	public Node MergeSort(Node headOriginal) 
	{ 
    		if (headOriginal == null || headOriginal.next == null) 
			return headOriginal; 
   		Node a = headOriginal;
		Node b = headOriginal.next; 
    		while ((b != null) && (b.next != null)) 
      		{ 
			headOriginal = headOriginal.next; 
			b = (b.next).next; 
		} 
    		b = headOriginal.next; 
		headOriginal.next = null; 
		return merge(MergeSort(a), MergeSort(b));
		 
	}	 

	public Node merge(Node a, Node b) 
  	{ 
		Node temp = new Node(); 
		Node head = temp;
		Node c = head; 
    		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; 
    		return head.next; 
  	} 
}
class LinkedListBlog
{
	public static void main(String[] args)
	{
		LinkedList object = new LinkedList();
		object.insert(30);
		object.insert(10);
		object.insert(50);
		object.insert(20);
		object.insert(5);
		object.insert(8);
		object.display();
		System.out.println("The list after merge sort O(nlog(n))");
		object.append(object.MergeSort(object.extractFirst()));
		object.display();
	}
}

OUTPUT:

~$ java LinkedListBlog
List items from first to last :
[8]
[5]
[20]
[50]
[10]
[30]

The list after merge sort O(nlog(n))
List items from first to last :
[5]
[8]
[10]
[20]
[30]
[50]

2 responses to “MergeSort of a Linked List – Java

  1. Afif June 2, 2013 at 5:48 am

    can you explain me what the function of line 64 headOriginal.next = null?
    thank you 🙂

  2. SongMi October 31, 2013 at 5:52 am

    What if I’m having my they of the data my node holds is ” object” how shall I compare the data ?
    (help will be appreciated!)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: