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

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

1. package com.instanceofjava.mergesortalgorithm;
2. 
   
3. public class MergeSortAlgorithm {
4. 
   
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");
13. 
    
14.        for(int i:inputArr){
15.           System.out.print(i);
16.            System.out.print(" ");
17. }
18. 
    
19.  MergeSortAlgorithm mergesortalg = new MergeSortAlgorithm();
20. 
    
21.        mergesortalg.sort(inputArr);
22.        System.out.println();
23. 
    
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[]) {
32. 
    
33.        this.resarray = inputArray;
34.        this.length = inputArray.length;
35.        this.tempMergArray = new int[length];
36.        doMergeSort(0, length - 1);
37. 
    
38. }
39.  
40. private void doMergeSort(int lowerIndex, int higherIndex) {
41.         
42.     if (lowerIndex < higherIndex) {
43. 
    
44.    int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
45. 
    
46.            //to sort left half of the array
47.    doMergeSort(lowerIndex, middle);
48. 
    
49.            // to sort right half of the array
50.    doMergeSort(middle + 1, higherIndex);
51. 
    
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.        }
62. 
    
63.        int i = lowerIndex;
64.        int j = middle + 1;
65.        int k = lowerIndex;
66. 
    
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.       }
77. 
    
78.      while (i <= middle) {
79.         resarray[k] = tempMergArray[i];
80.            k++;
81.            i++;
82.        }
83.    }
85. 
    
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