In this post, we will learn How to write a Merge sort program in Java?
Merge sort is very much efficient than the simple sorting algorithms like the bubble sort, selection sort, and insertion sort. the only drawback is that it requires an additional array along with the input array that is sorted.
How to merge sort works
Merge sort is usually working on the concept of merging two sorted arrays to create another array which is also sorted.
Now the question is that how do we get sorted arrays which are merged?
Since the merge sort follows the divide and conquer algorithm so here the idea is to divide the input array into two halves then each of these halves is also further divided into halves and so on until we get sub-arrays with only one element which is considered a sorted array.
At that point we start merging these sub-arrays from two single element sub-arrays then we create a sorted merged array of two elements. Then two such sorted sub-arrays of two elements are merged and create a sorted array of four elements and so on until you have a sorted array of all the elements.
Since in this algorithm array is recursively divided into two halves so this division process can be written as a recursive method where the base case becomes the point when we have sub-arrays with only one element each.
To Understand Merge sort, let us walk through an example.
We know that the merge sort first divides the whole array iteratively into equal halves unless the atomic values are achieved. We see here that an array of 8 items is divided into two arrays of size 4.
This does not change the sequence of appearance of items in the original array, now we divide these two arrays into halves.
We further divide these arrays and we achieve atomic values that can no more be divided.
Now, we combine them in exactly the same manner as they were broken down
We first compare the element for each array and then combine them into another array in a sorted manner. we see that 54 and 26 in the target array of 2 values we put 26 first followed by 54
Similarly, we compared 93 and 17 and in the target array of 2 values, we put 17 first followed by 93. On similar lines. We change the order of 77 and 31 whereas 44 and 55 are placed sequentially.
In the next iteration of the combining phase, we compare lists of two data values and merge them into an array of found data values placing all in sorted order.
After the final margin, the array should look like this:
The overall flow of the above discussion can be depicted as:
Source code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
package com.kkjavatutorials.client; /** * Java program for Merge sorting * @author KK JavaTutorials */ public class MergeSortTest { public static void main(String[] args) { int[] inputArr = {54,26,93,17,77,31,44,55}; mergeSort(inputArr, 0, inputArr.length-1); System.out.println("Array is sorted using Merge Sort"); for(int element : inputArr){ System.out.print(element + " "); } } private static void mergeSort(int[] intArr, int start, int end){ //Base case if (start == end){ return; }else{ //Get middle point for dividing the array int middle = (start + end)/2; mergeSort(intArr, start, middle); mergeSort(intArr, middle+1, end); mergeSubArrays(intArr, start, middle, end); } } private static void mergeSubArrays(int[] arr, int start, int middle, int end){ /*We have create two temporary arrays which will pertain two halves that are being merged and add elements to them*/ int subArrayFirstLength = middle - start + 1; int subArraySecondLength = end - middle; int[] temp1 = new int[subArrayFirstLength]; int[] temp2 = new int[subArraySecondLength]; for(int i = 0; i < subArrayFirstLength; i++){ temp1[i] = arr[start + i]; } for(int j = 0; j < subArraySecondLength; j++){ temp2[j] = arr[middle + 1 + j]; } int i =0; int j = 0; //Now merge two temporary arrays while((i < subArrayFirstLength) && (j < subArraySecondLength)){ if(temp1[i] < temp2[j]){ arr[start] = temp1[i++]; }else{ arr[start] = temp2[j++]; } start++; } //If there are more elements while(i < subArrayFirstLength){ arr[start++] = temp1[i++]; } while(j < subArraySecondLength){ arr[start++] = temp2[j++]; } } } |
The output of this program:
Array is sorted using Merge Sort
17 26 31 44 54 55 77 93
Performance of merge sort:
In merge sort usually, there is a sub-division of arrays and for each sub-division, there is merging. Number of levels (subdivisions of the array) can be calculated as– (log n + 1)
For example, log of 8 base 2 is 3, so log8 + 1 = 4
Which is equivalent to 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*(log n + 1). we can discard the 1 so the time complexity of merge sort is O(n log n).
Merge sort is not an “in-place” sorting algorithm because it requires extra space and auxiliary space required is equal to the number of elements in the original array so the space complexity of merge sort is O(n).
You May Also Like:
What is Sorting and why is Sorting Necessary?
Classification of Sorting Algorithms
Java program for Bubble Sort using Iterative Approach
Java program for Bubble Sort using recursive Approach
How to Write a Java program for Selection Sort in Java
How to Write a Java program for Insertion Sort in java?
Tree Sort Using Binary Search Tree in Java
That’s all about How to write a Merge sort program in Java?
If you have any feedback or suggestion please feel free to drop in below comment box.