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:
Lớp Collections trong Java (Collections Utility Class)
Java Program to Generate Date Between Given Range
Comparing getPath(), getAbsolutePath(), and getCanonicalPath() in Java
Jackson Annotation Examples
Updating your Password
Java – Reader to String
Converting Between a List and a Set in Java
Hướng dẫn Java Design Pattern – Observer
Upload and Display Excel Files with Spring MVC
Spring Boot - Database Handling
A Guide to the ViewResolver in Spring MVC
Guide to ThreadLocalRandom in Java
Weak References in Java
Date Time trong Java 8
Setting a Request Timeout for a Spring REST API
Java NIO2 Path API
Java Program to Perform Uniform Binary Search
Introduction to Project Reactor Bus
Spring REST with a Zuul Proxy
Spring’s RequestBody and ResponseBody Annotations
Thao tác với tập tin và thư mục trong Java
Java Program to Implement Johnson’s Algorithm
Derived Query Methods in Spring Data JPA Repositories
Display Auto-Configuration Report in Spring Boot
Call Methods at Runtime Using Java Reflection
Spring Security Custom AuthenticationFailureHandler
Java Program to Generate a Random Subset by Coin Flipping
Quick Guide to the Java StringTokenizer
HttpClient 4 – Send Custom Cookie
Spring REST API with Protocol Buffers
An Introduction to ThreadLocal in Java
Java Perform to a 2D FFT Inplace Given a Complex 2D Array