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:
Giới thiệu luồng vào ra (I/O) trong Java
The HttpMediaTypeNotAcceptableException in Spring MVC
Java Program to Find the Longest Path in a DAG
Java Multi-line String
Spring REST API with Protocol Buffers
Programmatic Transaction Management in Spring
Hướng dẫn Java Design Pattern – Factory Method
Spring Boot: Customize the Jackson ObjectMapper
Java Program to Implement Suffix Tree
Primitive Type Streams in Java 8
Java Program to Perform Finite State Automaton based Search
Java Program to Use Boruvka’s Algorithm to Find the Minimum Spanning Tree
Converting between an Array and a List in Java
Java Program to Perform Inorder Non-Recursive Traversal of a Given Binary Tree
Quick Guide on Loading Initial Data with Spring Boot
How to Convert List to Map in Java
Java Program to Implement the Monoalphabetic Cypher
Form Validation with AngularJS and Spring MVC
Rabin-Karp Algorithm for string matching
Java Program to implement Array Deque
Comparing Objects in Java
Java Program to Implement the Vigenere Cypher
Java Program to implement Dynamic Array
Java Program to Implement the MD5 Algorithm
New Features in Java 10
Java Program to Generate All Pairs of Subsets Whose Union Make the Set
Spring Cloud AWS – S3
Java Program to Implement EnumMap API
Java Program to Generate Date Between Given Range
Integer Constant Pool trong Java
Different Ways to Capture Java Heap Dumps
Java – Write an InputStream to a File