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.

  1. //This is a java to sort numbers of Linked List using Merge Sort
  2. import java.util.Random;
  3.  
  4. class Node 
  5. {
  6.     public int item;
  7.     public Node next;
  8.  
  9.     public Node(int val) 
  10.     {
  11.         item = val;
  12.     }
  13.  
  14.     public Node() 
  15.     {}
  16.  
  17.     public void displayNode() 
  18.     {
  19.         System.out.print("[" + item + "] ");
  20.     }
  21. }
  22.  
  23. class LinkedList 
  24. {
  25.     private Node first;
  26.  
  27.     public LinkedList() 
  28.     {
  29.         first = null;
  30.     }
  31.  
  32.     public boolean isEmpty() 
  33.     {
  34.         return (first == null);
  35.     }
  36.  
  37.     public void insert(int val)
  38.     {
  39.         Node newNode = new Node(val);
  40.         newNode.next = first;
  41.         first = newNode;
  42.     }
  43.  
  44.     public void append(Node result) 
  45.     {
  46.         first = result;
  47.     }
  48.  
  49.     public void display() 
  50.     {
  51.         Node current = first;
  52.         while (current != null) 
  53.         {
  54.             current.displayNode();
  55.             current = current.next;
  56.         }
  57.         System.out.println("");
  58.     }
  59.  
  60.     public Node extractFirst() 
  61.     {
  62.         return first;
  63.     }
  64.  
  65.     public Node MergeSort(Node headOriginal) 
  66.     {
  67.         if (headOriginal == null || headOriginal.next == null)
  68.             return headOriginal;
  69.         Node a = headOriginal;
  70.         Node b = headOriginal.next;
  71.         while ((b != null) && (b.next != null)) 
  72.         {
  73.             headOriginal = headOriginal.next;
  74.             b = (b.next).next;
  75.         }
  76.         b = headOriginal.next;
  77.         headOriginal.next = null;
  78.         return merge(MergeSort(a), MergeSort(b));
  79.     }
  80.  
  81.     public Node merge(Node a, Node b) 
  82.     {
  83.         Node temp = new Node();
  84.         Node head = temp;
  85.         Node c = head;
  86.         while ((a != null) && (b != null)) 
  87.         {
  88.             if (a.item <= b.item) 
  89.             {
  90.                 c.next = a;
  91.                 c = a;
  92.                 a = a.next;
  93.             }
  94.             else 
  95.             {
  96.                 c.next = b;
  97.                 c = b;
  98.                 b = b.next;
  99.             }
  100.         }
  101.         c.next = (a == null) ? b : a;
  102.         return head.next;
  103.     }
  104. }
  105.  
  106. class Merge_Sort 
  107. {
  108.     public static void main(String[] args) 
  109.     {
  110.         LinkedList object = new LinkedList();
  111.         Random random = new Random();
  112.         int N = 20;
  113.         for (int i = 0; i < N; i++)
  114.             object.insert(Math.abs(random.nextInt(100)));
  115.  
  116.         System.out.println("List items before sorting :");
  117.         object.display();
  118.         object.append(object.MergeSort(object.extractFirst()));
  119.         System.out.println("List items after sorting :");
  120.         object.display();
  121.     }
  122. }

Output:

advertisement
$ 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.

advertisement
advertisement

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

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter