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 Program to Implement Interpolation Search Algorithm
Hashing a Password in Java
Spring Boot - Eureka Server
So sánh HashMap và HashSet trong Java
Java Map With Case-Insensitive Keys
Java Program to Create the Prufer Code for a Tree
Java Program to Implement Splay Tree
Java Program to Permute All Letters of an Input String
Java – Reader to InputStream
Lập trình hướng đối tượng (OOPs) trong java
Object cloning trong java
Java Program to Find the Median of two Sorted Arrays using Binary Search Approach
Java Program to Implement Graham Scan Algorithm to Find the Convex Hull
Java Program to Implement Bit Array
Java Program to Implement Gauss Jordan Elimination
The DAO with JPA and Spring
Java Program to Implement Circular Doubly Linked List
Java equals() and hashCode() Contracts
Java Program to implement Bi Directional Map
So sánh HashMap và Hashtable trong Java
Java Program to Implement Sorted Doubly Linked List
Sử dụng JDBC API thực thi câu lệnh truy vấn dữ liệu
Creating Docker Images with Spring Boot
Java Program to Find kth Smallest Element by the Method of Partitioning the Array
Java Program to Implement the Bin Packing Algorithm
Vector trong Java
Lớp lồng nhau trong java (Java inner class)
Batch Processing with Spring Cloud Data Flow
Java Program to Implement Stack using Linked List
Spring Boot - Thymeleaf
Java Program to Convert a Decimal Number to Binary Number using Stacks
Request a Delivery / Read Receipt in Javamail