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]
Related posts:
Java CyclicBarrier vs CountDownLatch
Hướng dẫn Java Design Pattern – Abstract Factory
Simple Single Sign-On with Spring Security OAuth2
Java Program to Check if it is a Sparse Matrix
Runnable vs. Callable in Java
Java Program to Implement Floyd Cycle Algorithm
Introduction to Spring Cloud Netflix – Eureka
Chuyển đổi Array sang ArrayList và ngược lại
Spring Boot - Actuator
Introduction to Project Reactor Bus
Using Spring ResponseEntity to Manipulate the HTTP Response
Hướng dẫn Java Design Pattern – Proxy
Giới thiệu Design Patterns
Java Program to find the maximum subarray sum O(n^2) time(naive method)
A Quick Guide to Using Keycloak with Spring Boot
Java Program to Permute All Letters of an Input String
Hướng dẫn Java Design Pattern – State
Spring Cloud – Bootstrapping
Guide to BufferedReader
Spring Boot - Creating Docker Image
Introduction to Java Serialization
Spring RequestMapping
Java Program to Find the Minimum Element of a Rotated Sorted Array using Binary Search approach
Period and Duration in Java
Java Convenience Factory Methods for Collections
Retrieve User Information in Spring Security
@Before vs @BeforeClass vs @BeforeEach vs @BeforeAll
Sử dụng CyclicBarrier trong Java
How to Implement Caching using Adonis.js 5
Convert Hex to ASCII in Java
Intro to Inversion of Control and Dependency Injection with Spring
Getting the Size of an Iterable in Java