Merge Sort In Java

Introduction to Merge Sort in Java

Merge Sort in Java is one of the Sorting methods. Sorting in any programming language means arranging the data in a sequential manner. For example, the arrangement might be in Ascending order or in Descending order. It completely depends on the user as to what he/she wants the order to be. Sorting is used for not only numbers but also in the case of alphabets and names. For example, sorting is used in allotting roll numbers to students in a class. Also, the person who comes first is allotted Rank 1 according to the sorting algorithm. Sorting can be applied to either rank, weight, height, and even to the names of the respective persons in general. There are a lot of sorting techniques in Java that are used extensively by coders and programmers to ensure that all the possible ways of arranging data are looked after.

Some of the popular techniques used in Java for sorting algorithms are described below.

• Bubble sort
• Selection sort
• Insertion sort
• Heap sort
• Merge sort

Apart from the above-mentioned techniques, there are also other techniques that can be used for sorting data sequentially, such as Quicksort.

Working of  Merge Sort In Java

In Merge Sort in Java, we will see the working of the Merge Sort mechanism invented by John Von Neumann in the year 1945, which is used in Java to arrange data sequentially. Merge Sort In Java is quite similar to the Quick Sort mechanism. It is also referred to as a Divide and Conquer algorithm. In simple words, it divides the array into two halves. After that, it sorts the two arrays in a respective order as desired by the user. Then finally merges the two halves together, and it easily becomes a complete single sorted array. Now, suppose there is an array called arr[]. The merge sort mechanism divides the array first into two equal halves. Then it sorts the respective halves getting a sorted array at each end. Finally, the two halves are also equated to whether the left index is greater than the right or vice versa, and then the number is put into the array. In this way, the array is sorted.

The below diagram shows how an array is sorted using merge sort.

 

Example #1

In the first example, we are going to see a series of numbers being sorted in an array. Numbers are the easiest to sort as there are no ASCII values associated with numbers, as in alphabets or names. The following program shows the sorting in merge sort fashion sorting numbers in ascending order. There are two arrays, that is, the Left Array and the Right Array. The array has 10 numbers that have been arranged in ascending order, that is, from smallest to largest.

Code

import java.util.*;
public class Main
{
void merge(int arr[], int beg, int mid, int end)
{
int l = mid - beg + 1;
int r = end - mid;
int LeftArray[] = new int [l];
int RightArray[] = new int[r];
for(int i=0; i<l; ++i)
LeftArray[i] = arr[beg + i];
for(int j=0; j<r; ++j)
RightArray[j] = arr[mid + 1+ j];
int i = 0, j = 0;
int k = beg;
while(i<l&&j<r)
{
if(LeftArray[i] <= RightArray[j])
{
arr[k] = LeftArray[i];
i++;
}
else
{
arr[k] = RightArray[j];
j++;
}
k++;
}
while(i<l)
{
arr[k] = LeftArray[i];
i++;
k++;
}
while(j<r)
{
arr[k] = RightArray[j];
j++;
k++;
}
}
void sort(int arr[], int beg, int end)
{
if(beg<end)
{
int mid = (beg+end)/2;
sort(arr, beg, mid);
sort(arr , mid+1, end);
merge(arr, beg, mid, end);
}
}
public static void main(String args[])
{
int arr[] = {90,23,101,45,65,23,67,89,34,23};
MyMergeSort ob = new MyMergeSort();
sort(arr, 0, arr.length-1);
System.out.println("\nSorted array");
for(int i =0; i<arr.length; i++)
{
System.out.println(arr[i]+"");
}
}
}

Also, the sample output is shown below. The code is run using the Blue J platform, which smoothly generates the Sorted array in Ascending order.

Output

Example #2

In the second example, we are going to see them working on how alphabets or names or sorted using the Merge sort technique in Java. In the following program, we take the names of persons in any random order. The individual mergeSort() first sorts the names in alphabetical order. Secondly, the LeftMergeSort() and the RightMergeSort() are compared to see which name would be alphabetically earlier or later.

Code

import java.util.*;
public class NewClass {
public static void main(String[] args) {
String[] OneGo = { "Kring", "Panda", "Soliel", "Darryl", "Chan", "Matang", "Jollibee.", "Inasal" };
String[] TwoGo = { "Minnie", "Kitty", "Madonna", "Miley", "Zoom-zoom", "Cristine", "Bubbles", "Ara", "Rose", "Maria" };
String[] nameGo = new String[OneGo.length + TwoGo.length];
mergeSort(OneGo);
mergeSort(TwoGo);
merge(nameGo, OneGo, TwoGo);
mergeSort(nameGo);
//Arrays.sort(names);
for (String ClassThree: nameGo) {
System.out.println(ClassThree);
}
}
public static void mergeSort(String[] nameGo) {
if (nameGo.length > 1) {
String[] leftGo = new String[nameGo.length / 2];
String[] rightGo = new String[nameGo.length - nameGo.length / 2];
for (int so = 0; so < leftGo.length; so++) {
leftGo[so] = nameGo[so];
}
for (int ki = 0; ki < rightGo.length; ki++) {
rightGo[ki] = nameGo[ki + nameGo.length / 2];
}
mergeSort(leftGo);
mergeSort(rightGo);
merge(nameGo, leftGo, rightGo);
}
}
public static void merge(String[] nameH, String[] leftH, String[] rightH) {
int as = 0;
int bs = 0;
for (int i = 0; i < nameH.length; i++) {
if (bs >= rightH.length || (as < leftH.length && leftH[as].compareToIgnoreCase(rightH[bs]) < 0)) {
nameH[i] = leftH[as];
as++;
} else {
nameH[i] = rightH[bs];
bs++;
}
}
}
}

The sample output in this program is also shown below, which sorts the names in alphabetical order.

Output

Conclusion

In the article, we see how mergers sort works and sorts numbers and names in alphabetical order. Merge sort is very similar to Quick Sort. Merge sort is relatively easy to use than other sorting techniques. It is unlike the Selection sort, which compares each and every element to each other. Merge sort is used in Java, C, C++, Python, and many other programming languages for its varied benefits. It is used in FMCG companies where products have different labels and numbers assigned to them, telecommunication companies, manufacturing, and chemical industries. It is a very famous sorting technique because of its various usage in numerous places. 

Recommended Article

This has been a guide to Merge Sort In Java. Here we discuss an introduction to Merge Sort it working along with an example. You can also go through our other suggested articles to learn more –

1. Merge Sort in JavaScript
2. Heap Sort in Python
3. Insertion Sort in JavaScript
4. Merge Sort in Python