Java Program to Implement Merge Sort Algorithm
What is a Sorting?
In the Article, we will write a Program to Implement the Merge Sort and discuss the Implementation of the Merge Sort Algorithm.
Sorting algorithms are used to rearrange the items in a list or array so that they are in a specific order. There are many different sorting algorithms, each with its own set of trade-offs in terms of efficiency, speed, and complexity. Some common sorting algorithms include bubble sort, insertion sort, selection sort, merge sort, quick sort, and heap sort.
Sorting in Java:
In Java, there are several ways to sort elements:
- Using the sort() method of the java.util.Arrays class: This method sorts the elements of an array in ascending order. It can be used to sort arrays of primitive data types (such as int, char, etc.) as well as arrays of objects (such as String, etc.).
- Using the Collections.sort() method: This method sorts the elements of a List in ascending order. It can be used to sort Lists of objects (such as ArrayList, LinkedList, etc.).
- Using a sorting algorithm: There are several sorting algorithms that you can use to sort elements in Java. Some of the commonly used sorting algorithms are:
- Bubble sort
- Insertion sort
- Selection sort
- Merge sort
- Quick sort
Here is an example of how you can Implement the Merge Sort Algorithm.
Pseudo Code For Merge Sort Implementation:
MergeSort(int[] A, int start, int end)
if start < end then
int middle = (start + end) / 2
// recursively sort left subarray
MergeSort(A, start, middle)
// recursively sort right subarray
MergeSort(A, middle + 1, end)
// merge the two sorted subarrays
Merge(A, start, middle, end)
Merge(int[] A, int start, int middle, int end)
// size of left subarray
int n1 = middle - start + 1
// size of right subarray
int n2 = end - middle
// create left subarray
int[] Left = new int[n1 + 1]
// create right subarray
int[] Right = new int[n2 + 1]
// copy left subarray into L
for i = 0 to n1 - 1 do
Left[i] = A[start + i]
// copy right subarray into R
for j = 0 to n2 - 1 do
Right[j] = A[m + j + 1]
Left[n1] = INFINITY
Right[n2] = INFINITY
int i = 0, j = 0
// merge the two subarrays into A
for k = start to end do
if Left[i] <= Right[j] then
A[k] = Left[i]
i = i + 1
else
A[k] = Right[j]
j = j + 1
Program For Merge Sort Implementation:
import java.util.*;
public class Main{
public static void mergeSort(int[] arr, int start, int end) {
if (start < end) {
// Middle element
int mid = (start + end) / 2;
// merge left side
mergeSort(arr, start, mid);
// merge right side
mergeSort(arr, mid + 1, end);
// merge both sides
merge(arr, start, mid, end);
}
}
public static void merge(int[] arr, int start, int mid, int end) {
int n1 = mid - start + 1;
int n2 = end - mid;
int[] L = new int[n1 + 1];
int[] R = new int[n2 + 1];
for (int i = 0; i < n1; i++) {
L[i] = arr[start + i];
}
for (int j = 0; j < n2; j++) {
R[j] = arr[mid + j + 1];
}
L[n1] = Integer.MAX_VALUE;
R[n2] = Integer.MAX_VALUE;
int i = 0, j = 0;
for (int k = start; k <= end; k++) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
}
}
public static void main(String[] args) {
int[] arr = { 5, 1, 9, 3, 7, 4, 8, 6, 2 };
System.out.println("Original array: " + Arrays.toString(arr));
mergeSort(arr, 0, arr.length - 1);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
}
Output: Original array: [5, 1, 9, 3, 7, 4, 8, 6, 2] Sorted array: [1, 2, 3, 4, 5, 6, 7, 8, 9]
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment