Merge Sort Java Program

This tutorial shows how to write Merge sort program in Java. Merge sort is termed as a “divide and conquer algorithm” and it is considered to be more efficient than the simple sort algorithms like selection sort and insertion sort.

Merge sort algorithm

The algorithm for merge sort is based on the process of merging where two sorted arrays are merged to form a large sorted array. To merge the smaller arrays first you do need to divide your array into smaller arrays too so effectively Merge sort is a two step process.

  1. Divide the input array into two halves this process is carried out recursively until you get sub-arrays with only one element which is the base case for the recursive division. These sub-arrays of one element each are considered as sorted arrays.
  2. In this step these smaller arrays are sorted and merged recursively until you again get the larger sorted array. Merging process starts from bottom where a pair of single element sub-arrays are sorted and merged to create an array of two elements. Then a pair of such sorted sub-arrays of two elements are merged to create a sorted array of four elements and so on.

Following image shows the sub-division process for an array {43, 39, 54, 61, 81, 55, 92, 7}

Merge sort algorithm

At this point base case is encountered which starts the merging process that is explained using the following image.
Merge sort Java

Merge Sort Java program

public class MergeSort {
  public static void main(String[] args) {
    int[] arr = {43, 39, 54, 61, 81, 55, 92, 7, 0, 15, 112, 10};
    System.out.println("Original array- " + Arrays.toString(arr));
    MergeSort ms = new MergeSort();
    ms.mergeSortRecursive(arr, 0, arr.length-1);
    System.out.println("Sorted array after merge sorting- " + Arrays.toString(arr));
  }
	
  private void mergeSortRecursive(int[] arr, int start, int end){
    //base case
    if (start == end){
        return;
    }else{
      // Middle point of the array
      int middle = (start + end)/2;  
      // divide array into two parts using middle point
      mergeSortRecursive(arr, start, middle);        
      mergeSortRecursive(arr, middle+1, end);
      // call merge process
      merge(arr, start, middle, end);
    }
  }
    
  private void merge(int[] arr, int start, int middle, int end){
    // Create two temp arrays for two halves
    int temArray1Length = middle - start + 1;
    int temArray2Length = end - middle;
    int[] temp1 = new int[temArray1Length];
    int[] temp2 = new int[temArray2Length];
    for(int i = 0; i < temArray1Length; i++){
      temp1[i] = arr[start + i];
    }
    for(int j = 0; j < temArray2Length; j++){
      temp2[j] = arr[middle + 1 + j];
    }

    int i =0;        
    int j = 0;
    // merging process, merge two temp arrays put the 
    // sorted elements in original array 
    while((i < temArray1Length) && (j < temArray2Length)){
      if(temp1[i] < temp2[j]){
        arr[start] = temp1[i++];
      }else{
        arr[start] = temp2[j++];
      }
      start++;
    }
    // Add left over elements from temp arrays
    while(i < temArray1Length){
      arr[start++] = temp1[i++];
    }
    while(j < temArray2Length){
      arr[start++] = temp2[j++];
    }
  }
}

Output

Original array- [43, 39, 54, 61, 81, 55, 92, 7, 0, 15, 112, 10]
Sorted array after merge sorting- [0, 7, 10, 15, 39, 43, 54, 55, 61, 81, 92, 112]

Merge sort time and space complexity

Time complexity of merge sort is O(n*logn) where logn is the complexity of sub-dividing the array and n is the complexity for merging n elements at each level.

Space complexity of merge sort is O(n) as extra space for temp array is required which is equal to the length of the input array.

Related Posts

That’s all for the topic Merge sort Java Program. If something is missing or you have something to share about the topic please write a comment.


You may also like

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.