Java Program to Implement Merge Sort Algorithm on Linked List

Code:

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 + "] ");
    }
}

class LinkedList 
{
    private Node first;

    public LinkedList() 
    {
        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;
    }

    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 Merge_Sort 
{
    public static void main(String[] args) 
    {
        LinkedList object = new LinkedList();
        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:

List items before sorting :
[41] [11] [6] [13] [41] [62] [26] [46] [71] [16] [52] [57] [23] [81] [25] [4] [20] [75] [68] [51] 
List items after sorting :
[4] [6] [11] [13] [16] [20] [23] [25] [26] [41] [41] [46] [51] [52] [57] [62] [68] [71] [75] [81]




More Java Programs: