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 InputStream to String
Guide to the Volatile Keyword in Java
Setting Up Swagger 2 with a Spring REST API
Java Program to Test Using DFS Whether a Directed Graph is Weakly Connected or Not
Java Program to Implement Ternary Search Algorithm
Java Program to Find Second Smallest of n Elements with Given Complexity Constraint
Anonymous Classes in Java
List Interface trong Java
Iterating over Enum Values in Java
Kiểu dữ liệu Ngày Giờ (Date Time) trong java
Java Program to Implement Pollard Rho Algorithm
Java Program to Perform Preorder Non-Recursive Traversal of a Given Binary Tree
Guide to System.gc()
Spring Boot - Exception Handling
Java Program to Implement Multi-Threaded Version of Binary Search Tree
How to Replace Many if Statements in Java
Rate Limiting in Spring Cloud Netflix Zuul
Java Program to Implement Park-Miller Random Number Generation Algorithm
Join and Split Arrays and Collections in Java
Properties with Spring and Spring Boot
Guide to DelayQueue
Introduction to Project Reactor Bus
Getting Started with GraphQL and Spring Boot
ETL with Spring Cloud Data Flow
Java Program to Perform Right Rotation on a Binary Search Tree
A Custom Data Binder in Spring MVC
Java Program to Construct an Expression Tree for an Prefix Expression
How to Find an Element in a List with Java
Java Program to find the maximum subarray sum using Binary Search approach
Java Program to Perform integer Partition for a Specific Case
Spring Security Login Page with React
Hướng dẫn sử dụng Java Generics