In this post we’ll see how to write Merge sort program in Java. Merge sort is much more efficient than the simple sort algorithms like bubble sort and insertion sort. One drawback is that it requires an additional array along with the original array that is sorted.
How merge sort works
Merge sort works on the concept of merging two sorted arrays to create another array which is also sorted.
Now the question is how do you get sorted arrays which are merged? Since merge sort is also termed as divide and conquer algorithm so the idea is to divide the input array into two halves then each of these halves are further divided into halves and so on until you get sub-arrays with only one element which is considered a sorted array.
At that point you start merging these sub-arrays, from two single element sub-arrays you create a sorted merged array of two elements. Then two such sorted sub-arrays of two elements are merged to create a sorted array of four elements and so on until you have a sorted array of all the elements.
Since array is recursively divided into two halves so this division process can be written as a recursive method where base case becomes the point when you have sub-arrays with only one element each.
Let’s try to understand with an example where we have an input array as given below.
int[] intArr = {21, 11, 33, 70, 5, 25, 65, 55};
The process of recursive calls to divide the array into halves can be explained using the following image.
At this point merge process starts which merges two sorted arrays to create another sorted array, this merging process can be explained using the following image.
Merge Sort Java program
In the merge sort program there is a method mergeSortRecursive which is called recursively to divide the array.
Merge method merges the two sub-arrays to create a sorted array.
public class MergeSort {
public static void main(String[] args) {
int[] intArr = {47, 85, 620, 3456, -7, 10, 4500, 106, -345, 1000, 67, 80, 5500, 34, 78, 782, 4, 0, 99, 190};
MergeSort ms = new MergeSort();
ms.mergeSortRecursive(intArr, 0, intArr.length-1);
System.out.println("Sorted array after merge sort- ");
for(int num : intArr){
System.out.print(num + " ");
}
}
private void mergeSortRecursive(int[] intArr, int lower, int upper){
//base case
if (lower == upper){
return;
}else{
// get mid point for division of array
int middle = (lower + upper)/2;
mergeSortRecursive(intArr, lower, middle);
mergeSortRecursive(intArr, middle+1, upper);
merge(intArr, lower, middle, upper);
}
}
private void merge(int[] intArr, int lower, int middle, int upper){
/** Create two temp arrays pertaining to two halves that
are being merged and add elements to them */
int subArrayOneLength = middle - lower + 1;
int subArrayTwoLength = upper - middle;
int[] temp1 = new int[subArrayOneLength];
int[] temp2 = new int[subArrayTwoLength];
for(int i = 0; i < subArrayOneLength; i++){
temp1[i] = intArr[lower + i];
}
for(int j = 0; j < subArrayTwoLength; j++){
temp2[j] = intArr[middle + 1 + j];
}
int i =0;
int j = 0;
// merging process, merge two temp arrays
while((i < subArrayOneLength) && (j < subArrayTwoLength)){
if(temp1[i] < temp2[j]){
intArr[lower] = temp1[i++];
}else{
intArr[lower] = temp2[j++];
}
lower++;
}
// If there are more elements
while(i < subArrayOneLength){
intArr[lower++] = temp1[i++];
}
while(j < subArrayTwoLength){
intArr[lower++] = temp2[j++];
}
}
}
Output
Sorted array after merge sort- -345 -7 0 4 10 34 47 67 78 80 85 99 106 190 620 782 1000 3456 4500 5500
Performance of merge sort
In merge sort there is subdivision of arrays and for each sub-division there is merging. Number of levels (subdivisions of array) can be calculated as– (logN + 1)
For example log of 8 base 2 is 3, so log8 + 1 = 4
Which is same as the number of halves for the array having 8 elements– 8 4 2 1.
At each level N elements are merged which makes the time complexity of merge sort as N*(logN + 1). we can discard the 1 so the time complexity of merge sort is O(N*logN).
Merge sort is not an in place sort algorithm as extra space is required. Auxiliary space required is equal to the number of elements in the original array so the space complexity of merge sort is O(N).
That's all for this topic Merge Sort Program in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!
>>>Return to Java Programs Page
Related Topics
You may also like-