In Java programming, there can be instances where the developer needs to sort the bulk entries. For instance, arranging or analyzing the randomly generated values. In such cases, the “merge sort” in Java is effective and quicker, thereby consuming less time to sort the longer entries or lists as compared to other algorithms i.e., “Bubble Sort”.
This blog will elaborate on the implementation of the “merge sort” algorithm in Java.
How to Implement a “Merge Sort” in Java?
The “merge sort” is based on the “divide and conquer” algorithm such that the array is divided into equal halves and then further subdivided till the division can no longer be done. After the array is subdivided, it is merged again based on the elements in a sorted(ascending) way.
Demonstration of the “Merge Sort” Algorithm
Let’s overview the below-provided code to understand the discussed concept:
public static void mergedArray(int[] leftArray,int[] rightArray, int[] finalArray,int leftarraySize, int rightarraySize){
int item=0,left=0,right = 0;
while(left<leftarraySize && right<rightarraySize){
if(leftArray[left]<rightArray[right]){
finalArray[item++] = leftArray[left++];
}
else{
finalArray[item++] = rightArray[right++];
}}
while(left<leftarraySize){
finalArray[item++] = leftArray[left++];
}
while(right<rightarraySize){
finalArray[item++] = rightArray[right++];
}}
In the above code allocated for merging, apply the following steps:
-
- Define a function named “mergedArray” having the stated parameters for left and right arrays, the original array and the sizes of the left and right arrays, respectively.
- In the function definition, initialize the stated values to apply a condition later in the code.
- In the next step, apply the combined “while” loop and “if” condition to check the condition for merging.
- It is such that if the element in the left array is smaller than that of the right array element at a particular index, then the merged array is appended with the left array element starting from left to right.
- In the other case, the right array element is appended.
- After that, apply the “while” loop to check if only elements in the left or right array are left and append them to the array accordingly.
Implementation
Now, let’s move on to the following snippet of code:
if (length < 2){return;}
int div = length / 2;
int [] lArray = new int[div];
int [] rArray = new int[length-div];
int temp = 0;
for(int i = 0;i<length;++i){
if(i<div){
lArray[i] = array[i];
}
else{
rArray[temp] = array[i];
temp = temp+1;
}}
divideArray(lArray,div);
divideArray(rArray,length-div);
mergedArray(lArray,rArray,array,div,length-div);
}
In this code implemented for dividing the passed array, perform the below-provided steps:
-
- Define the function “divideArray()” having the parameters pointing to the passed array and its length.
- Now, check for the condition such that the array length is not greater than “2”. If so, return the array as it is. Else, execute the further functionalities.
- After that, divide the array into two equal halves via its(array) passed length.
- In the next step, create two integer arrays based on the split length of the passed array.
- Now, append the left and right split arrays with the passed array elements.
- Lastly, invoke this function recursively upon these two split arrays which accumulate the copied data of the original passed array, and access the “mergedArray()” function that compares and sorts the left and right arrays.
Implementation
Now, overview the “main” code:
int [] mergesortArray = {30, 12, 46, 6, 17, 23};
divideArray(mergesortArray,mergesortArray.length);
for(int i =0; i< mergesortArray.length;++i){
System.out.print(mergesortArray[i]+ " "); }
}}
In the “main”, apply the following steps:
-
- Declare an array named “mergesortArray” that needs to be sorted.
- In the next step, invoke the function “divideArray()” by passing the declared array and its length via the “length” property, as its arguments, respectively.
- After that, iterate through the array and display the sorted array elements via the “for” loop.
- Algorithm: The provided array will be passed to the function “divideArray()” that splits the array and this function then invokes the function “mergedArray()” that merges the split arrays based on the contained elements.
Implementation
Entire Code
public static void mergedArray(int[] leftArray,int[] rightArray, int[] finalArray,int leftarraySize, int rightarraySize){
int item=0,left=0,right = 0;
while(left<leftarraySize && right<rightarraySize){
if(leftArray[left]<rightArray[right]){
finalArray[item++] = leftArray[left++];
}
else{
finalArray[item++] = rightArray[right++];
}}
while(left<leftarraySize){
finalArray[item++] = leftArray[left++];
}
while(right<rightarraySize){
finalArray[item++] = rightArray[right++];
}}
public static void divideArray(int [] array, int length){
if (length < 2){return;}
int div = length / 2;
int [] lArray = new int[div];
int [] rArray = new int[length-div];
int temp = 0;
for(int i = 0;i<length;++i){
if(i<div){
lArray[i] = array[i];
}
else{
rArray[temp] = array[i];
temp = temp+1;
}}
divideArray(lArray,div);
divideArray(rArray,length-div);
mergedArray(lArray,rArray,array,div,length-div);
}
public static void main( String args[] ) {
int [] mergesortArray = {30, 12, 46, 6, 17, 23};
divideArray(mergesortArray,mergesortArray.length);
for(int i =0; i< mergesortArray.length;++i){
System.out.print(mergesortArray[i]+ " "); }
}}
Output
In this output, it can be implied that the passed array is sorted appropriately.
Conclusion
The merge sort is based on the “divide and conquer” algorithm such that the array is subdivided into equal halves and merged again based on the sorted elements. The outcome of the algorithm is fetched in accordance with the original one in a sorted way. This blog discussed the implementation of the merge sort algorithm in Java.
