Merge Sort in Java

This tutorial explains merge sort algorithm with example implementation in java. It starts off with explaining how merge sort uses divide-and-conquer technique. This is followed by a step-by-step walkthrough showing how recursive merge sort can be used to used for ordering a 5 number list. Next we will go through java implementation of merge sort followed by its detailed explanation.

Merge Sort is a divide-and-conquer algorithm
Merge Sort comes under the category of divide-and-conquer algorithms. Divide-and-conquer algorithms work on the principle of dividing the problem into smaller, more manageable, sub-problems recursively until these sub-problems become simple enough to be solved directly. The solutions to these sub-problems are then merged in the reverse order in the recursive chain to obtain the final desired result.

You can see a whiteboard animation video explanation of how merge sort works and get a code walk-through in this YouTube video

Step-by-step walkthrough of how merge sort works
We will take up merge sort solution in the most optimised way i.e. recursively. Lets say the list to be sorted is [10, 5, 100, 1,10000].

Stage 1- DIVIDE
Recursive Call Level 1
We divide the list into 2 sub-lists [10,5] and [100,1,10000]. We then pick the left sub-list [10,5] and see that the size of the list > 1 . Its important to note at this point that list size of 1 is the boundary condition for recursiveness i.e. the recursive calls stop at the boundary condition and the solved sub-problems are returned back as results of recursive calls. So, since size of list [10,5] is > 1 hence we again make a recursive call for merge sorting of the left sub-list.

Recursive Call Level 1.1
Sub-list [10,5] is now the candidate for merge sort so it is now divided into 2 halves [10] and [5]. Now these two sub-lists are of size 1 which is the boundary condition as explained above. So these two sub-lists are assumed to be correctly merge sorted and returned. As they are returned they are merged in the correct order to produce the sorted sub-list [5,10].

Stage 2- CONQUER
This is the second stage of merge sort. During merging both of the sub-lists are read with individual pointers. The elements at the heads of the two sub-lists are compared and the lesser one is picked and pushed into a third list , called say the merged-list. The pointer for the sub-list from which the element was picked is moved forward to point to the next element.

Similarly, the right sub-list [100,1,10000] is merge sorted with multiple recursive calls to get [1,100,10000]  as the result.

The left and right sorted sub-lists are merged to get the final sorted list [1,5,10,100,10000].
Recursive Merge sort algorithm implemented in Java

Recursive Merge sort algorithm implemented in Java
package com.javabrahman.algorithms.sorts;
public class MergeSort {
 static int inputArray[] = { 10, 5, 100, 1,10000};
 
 public static int[] doMergeSort(int[] values) {
  if(values.length<=1){
   return values;
  }
  int mid=(values.length)/2;
  int[] left=new int[mid];
  int[] right=new int[(values.length)-mid];
  for(int leftCount=0;leftCount<mid;leftCount++){
   left[leftCount]=values[leftCount];
  }
  for(int rightCount=0;rightCount<((values.length)-mid); rightCount++){
   right[rightCount]=values[mid+rightCount];
  }
  return merge(doMergeSort(left),doMergeSort(right));
 }
 
 public static int[] merge(int[] left, int[]right){
  int leftCounter=0,rightCounter=0, mergedCounter=0;
  int merged[]=new int[left.length+right.length];
  while(leftCounter < left.length && rightCounter < right.length){
   if(left[leftCounter]<=right[rightCounter]){
     merged[mergedCounter]=left[leftCounter];
    leftCounter++;
    mergedCounter++;
   }else{
    merged[mergedCounter]=right[rightCounter];
    rightCounter++;
    mergedCounter++;
   }
  }
  while(leftCounter<left.length){
   merged[mergedCounter]=left[leftCounter];
   leftCounter++;
   mergedCounter++;
  }
  while(rightCounter<right.length){
   merged[mergedCounter]=right[rightCounter];
   rightCounter++;
   mergedCounter++;
  }
  return merged;
 }
 
 public static void printArray(int[] sortedArray) {
  for (int i = 0; i < sortedArray.length; i++) {
   System.out.print(" " + sortedArray[i]); 
  }
 }
 
 public static void main(String args[]) {
 System.out.print("Array Before Sorting->");
  printArray(inputArray);
  int sortedArray[]=doMergeSort(inputArray);
  System.out.print("\nArray After Sorting ->");
  printArray(sortedArray);
 }
}
 OUTPUT of the above code
Array Before Sorting-> 10 5 100 1 10000
Array After Sorting -> 1 5 10 100 10000
Explanation of the code

  • The doMergeSort() method is responsible for merge sorting of a list of elements passed to it. It does the following –
    • Divides the list passed to it into 2 lists – left and right.
    • Recursively calls doMergeSort() on the left and right sub-lists
    • It merges the left and right sub-lists by calling the merge() method
    • The boundary condition for this method is 1. I.e. if the size of the list being sorted by this method is 1 then the list is returned back as it is.
  • The merge() method iterates over the two sub-lists left and right passed to it and merges them in the correct sorting order.
  • Mechanism of merging – Merging of the sub-lists works as follows –
    1. Both of the sub-lists are read with individual pointers.
    2. The elements at the heads of the two sub-lists are compared and the lesser one is picked and pushed into a third list , called say the merged-list.
    3. The pointer for the sub-list from which the element was picked is moved forward to point to the next element.
  • The main() method orchestrates the sorting.
  • The instance element inputArray[] holds the list to be sorted.

Summary
In this tutorial on merge sort algorithm in java we understood the sorting algorithm’s divide-and-conquer nature, understood the algorithm’s working by a step-by-step walkthrough of sorting of a 5-number list, saw the java code for implementing recursive merge sort and finally understood the java program’s working in detail.

 

Digiprove sealCopyright © 2014-2016 JavaBrahman.com, all rights reserved.