• 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 merge sort in java


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

  1. package com.instanceofjava.mergesortalgorithm;

  2. public class MergeSortAlgorithm {

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

  11.        for(int i:inputArr){
  12.           System.out.print(i);
  13.            System.out.print(" ");
  14. }

  15.  MergeSortAlgorithm mergesortalg = new MergeSortAlgorithm();

  16.        mergesortalg.sort(inputArr);
  17.        System.out.println();

  18.        System.out.println("After sorting");
  19.        for(int i:inputArr){
  20.            System.out.print(i);
  21.            System.out.print(" ");
  22.        }
  23.  }
  24.     
  25. public void sort(int inputArray[]) {

  26.        this.resarray = inputArray;
  27.        this.length = inputArray.length;
  28.        this.tempMergArray = new int[length];
  29.        doMergeSort(0, length - 1);

  30. }
  31.  
  32. private void doMergeSort(int lowerIndex, int higherIndex) {
  33.         
  34.     if (lowerIndex < higherIndex) {

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

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

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

  40.            //merge two halfs
  41.     mergehalfs(lowerIndex, middle, higherIndex);
  42. }
  43. }
  44.  
  45. private void mergehalfs(int lowerIndex, int middle, int higherIndex) {
  46.  
  47.        for (int i = lowerIndex; i <= higherIndex; i++) {
  48.         tempMergArray[i] = resarray[i];
  49.        }

  50.        int i = lowerIndex;
  51.        int j = middle + 1;
  52.        int k = lowerIndex;

  53.   while (i <= middle && j <= higherIndex) {
  54.            if (tempMergArray[i] <= tempMergArray[j]) {
  55.             resarray[k] = tempMergArray[i];
  56.                i++;
  57.            } else {
  58.             resarray[k] = tempMergArray[j];
  59.                j++;
  60.            }
  61.            k++;
  62.       }

  63.      while (i <= middle) {
  64.         resarray[k] = tempMergArray[i];
  65.            k++;
  66.            i++;
  67.        }
  68.    }

  69. }

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 

Instance Of Java

We will help you in learning.Please leave your comments and suggestions in comment section. if you any doubts please use search box provided right side. Search there for answers thank you.
«
Next
Newer Post
»
Previous
Older Post

No comments

Leave a Reply

Select Menu