Merge sort algorithm in java with example program

  • Merge sort one of the recursive sorting algorithm.
  • First divide the list of unsorted elements in two two parts. left half and right half.

  • Divide the left part elements in to sub lists until it become single element.
  • Divide right half of array or list of elements in to sub lists until it becomes one element in list.
  • After dividing all elements in two parts in to single entity. 
  • Merge the elements into two by comparing lesser element will be first. apply same at right half
  • Merge all the elements in the left part until it become single sorted list
  • Now we have two sorted parts.
  • Means two parts sorted in ascending order and smaller element will be in first position.
  • Compare fist elements of two parts , lesser one should be takes first place in new sorted list
  • New sorted list or array having only one element now.
  • Compare two lists elements and place in sorting order and merge it. 
  • Finally we have all elements sorted.
  • Compared to remaining algorithms like selection sort, insertion sort and bubble sort  merge sort works faster.
  • Lets see what will be the time complexity of merge sort algorithm.

Time complexity of merge sort algorithm:


1.Best case  time complexity:      O(n log (n))
2.Average case time complexity: O(n log (n))
3.Worst case time complexity:    O(n log (n))
4.Worst case space complexity:  O(n)


Merge sort in java with explanation diagram

Implement%2Bmerge%2Bsort%2Bin%2Bjava


Program#1: Java program to implement merge sort algorithm data structure 

  1. package com.instanceofjava.mergesortalgorithm;

  3. public class MergeSortAlgorithm {

  5.    private int[] resarray;
  6.    private int[] tempMergArray;
  7.    private int length;
  8.  
  9.  public static void main(String a[]){
  10.          
  11.  int[] inputArr ={6,42,2,32,15,8,23,4};
  12.         System.out.println("Before sorting");

  14.        for(int i:inputArr){
  15.           System.out.print(i);
  16.            System.out.print(" ");
  17. }

  19.  MergeSortAlgorithm mergesortalg = new MergeSortAlgorithm();

  21.         mergesortalg.sort(inputArr);
  22.         System.out.println();

  24.         System.out.println("After sorting");
  25.         for(int i:inputArr){
  26.             System.out.print(i);
  27.             System.out.print(" ");
  28.         }
  29.  }
  30.      
  31. public void sort(int inputArray[]) {

  33.         this.resarray = inputArray;
  34.         this.length = inputArray.length;
  35.         this.tempMergArray = new int[length];
  36.         doMergeSort(0, length - 1);

  38. }
  39.  
  40. private void doMergeSort(int lowerIndex, int higherIndex) {
  41.          
  42.     if (lowerIndex < higherIndex) {

  44.    int middle = lowerIndex + (higherIndex - lowerIndex) / 2;

  46.             //to sort left half of the array
  47.    doMergeSort(lowerIndex, middle);

  49.             // to sort right half of the array
  50.    doMergeSort(middle + 1, higherIndex);

  52.             //merge two halfs
  53.     mergehalfs(lowerIndex, middle, higherIndex);
  54. }
  55. }
  56.  
  57. private void mergehalfs(int lowerIndex, int middle, int higherIndex) {
  58.  
  59.         for (int i = lowerIndex; i <= higherIndex; i++) {
  60.          tempMergArray[i] = resarray[i];
  61.         }

  63.         int i = lowerIndex;
  64.         int j = middle + 1;
  65.         int k = lowerIndex;

  67.   while (i <= middle && j <= higherIndex) {
  68.             if (tempMergArray[i] <= tempMergArray[j]) {
  69.              resarray[k] = tempMergArray[i];
  70.                 i++;
  71.             } else {
  72.              resarray[k] = tempMergArray[j];
  73.                 j++;
  74.             }
  75.             k++;
  76.       }

  78.      while (i <= middle) {
  79.          resarray[k] = tempMergArray[i];
  80.             k++;
  81.             i++;
  82.         }
  83.    }

  86. }

Output:

  1. Before sorting
  2. 6  42  2  32  15  8  23  4
  3. After sorting
  4. 2  4  6  8  15  23  32  42