» » » Merge sort algorithm in java with example program

# 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. 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