Java Program to Sort Linked List using Merge Sort

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

```
    }
```
```
}
```
```
 
```
```
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:

$ javac Merge_Sort.java
$ java Merge_Sort
 
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]

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

« Prev - Java Program to Perform Uniform Binary Search

» Next - Java Program to Perform Quick Sort on Large Number of Elements

Related Posts:

Recommended Articles: