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

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 After Sorting -> 1 5 10 100 10000

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

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

Copyright © 2014-2017 JavaBrahman.com, all rights reserved.