Thursday, December 13, 2018

Merge Sort Program in Java

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.

merge sort in java

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 program java

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

  1. Shell Sort Program in Java
  2. Radix Sort Program in Java
  3. How to Display Pyramid Patterns in Java - Part1
  4. Arrange Non-Negative Integers to Form Largest Number - Java Program
  5. How to Find All The Permutations of The Given String

You may also like-

  1. Running Dos/Windows Commands From Java Program
  2. Finding Duplicate Elements in an Array - Java Program
  3. How to Format Time in AM-PM Format - Java Program
  4. How to Sort an ArrayList in Descending Order in Java
  5. CopyOnWriteArrayList in Java
  6. Reflection in Java
  7. String in Java
  8. NameNode, DataNode And Secondary NameNode in HDFS