Merge Sort In Java

Introduction to Merge Sort in Java

Merge Sort in Java is one of the Sorting Method. Sorting in any programming language means to arrange the data in a sequential manner. 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. 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 which 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 algorithm are described below

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

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

Working of  Merge Sort In Java

In Merge Sort in Java, we are going to see the working of the Merge Sort mechanism invented by John Von Neumann in the year 1945 which is used in Java for the purpose of sequentially arranging data. 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, it merges the two halves together and it easily becomes a complete single sorted array. Now, suppose there is an array called arr[]. 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 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 that are associated with numbers as in the case of 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 which have been arranged in ascending order, that is, from smallest to largest.

Code

public class MyMergeSort
{
void merge(int arr[], int beg, int mid, int end)
{
intl = mid - beg + 1;
intr = end - mid;
intLeftArray[] = newint [l];
intRightArray[] = newint[r];
for(inti=0; i<l; ++i)
LeftArray[i] = arr[beg + i];
for(intj=0; j<r; ++j)
RightArray[j] = arr[mid + 1+ j];
inti = 0, j = 0;
intk = 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++;
}
}
voidsort(intarr[], int beg, int end)
{
if(beg<end)
{
intmid = (beg+end)/2;
sort(arr, beg, mid);
sort(arr , mid+1, end);
merge(arr, beg, mid, end);
}
}
publicstaticvoid main(String args[])
{
intarr[] = {90,23,101,45,65,23,67,89,34,23};
MyMergeSort ob = newMyMergeSort();
sort(arr, 0, arr.length-1);
out.println("\nSorted array");
for(inti =0; i<arr.length;i++)
{
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 merge sort works and sorts numbers and names both 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 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, in telecommunication companies, in manufacturing as well as in chemical industries. It is a very famous sorting technique because of its varies 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 example. You can also go through our other suggested articles to learn more –

1. Java Tools
2. Frameworks In Java
3. Destructor in Java
4. Guide to Merge Sort in JavaScript