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:
Converting String to Stream of chars
LIKE Queries in Spring JPA Repositories
Hướng dẫn Java Design Pattern – State
Automatic Property Expansion with Spring Boot
Spring Boot Annotations
Java Program to Implement AVL Tree
Spring Cloud – Bootstrapping
Java IO vs NIO
Java Program to Implement Sorted Circular Doubly Linked List
Hướng dẫn sử dụng Lớp FilePermission trong java
Java Program to Generate All Subsets of a Given Set in the Lexico Graphic Order
Spring Cloud AWS – S3
Java Program to Implement Aho-Corasick Algorithm for String Matching
Java Program to Implement Ford–Fulkerson Algorithm
Java Program to Test Using DFS Whether a Directed Graph is Weakly Connected or Not
Java Program to Check if a Given Set of Three Points Lie on a Single Line or Not
Integer Constant Pool trong Java
Java Program to Implement Circular Singly Linked List
New in Spring Security OAuth2 – Verify Claims
Java Program to Implement Gift Wrapping Algorithm in Two Dimensions
Java Program to Implement HashMap API
Truyền giá trị và tham chiếu trong java
Java Program to Implement Efficient O(log n) Fibonacci generator
Java Program to Implement Sorting of Less than 100 Numbers in O(n) Complexity
Performance Difference Between save() and saveAll() in Spring Data
Implementing a Runnable vs Extending a Thread
So sánh ArrayList và LinkedList trong Java
Compare Two JSON Objects with Jackson
Spring RestTemplate Request/Response Logging
How to Convert List to Map in Java
Creating a Web Application with Spring 5
Using Spring @ResponseStatus to Set HTTP Status Code